（或許你沒有聽說過dlut這個oj，但我要自豪的的說，她是我大工軟院最有愛的地方，沒有造作，有軟院acmer的信念，有歡笑，有一代代軟院acmer的付出！還有許多無節操的好玩的題！）好的，言歸正傳，作為這次唯一a掉的題，有些不甘，我晚做了3個小時，好吧！下次求突破。（不過還是9ms，目前最快，哈）
題目
舞美拉 wumela
舞美拉口頭禅：想要我的簽名嗎？ 星座：水瓶座 生日：1月28日 血型：A型 年齡：17歲 生肖：豬 身高：172公分 體重：49公斤 職業：歌手 興趣：跳舞、唱歌 寵物：波斯貓 最喜歡：吃中國菜 最讨厭：體重增加 偶像：小甜甜布蘭尼 語言：中文 中英混血女孩，雖然平時跟爸爸學了一點中文（國語），但不是很流暢。對音樂和舞蹈有着超乎常人的天賦，13歲就獲得了少女歌手大賽的冠軍，從此進入歌壇，憑借她甜美的歌聲和火爆優美的熱舞，很快成為少男少女們新的偶像，最新一場的個人演唱會吸引了數萬歌迷參加，據說連一向愛聽歌仔戲的阿土伯也喜歡聽她唱的歌，經常跟着MTV中的舞美拉邊唱邊跳，還差點扭了腰呢。 生活中的舞美拉心地善良，經常幫爸爸和媽媽做家務，自己的房間也總是裝扮地溫馨幹淨，有空的時候就去敬老院做義工，但這并不妨礙她愛美愛打扮，任何衣服經過她的巧手改裝，都以其别出心裁的新意成為少女們效仿的對象，她最大的志願就是成為一位時裝設計師。 由于人見人愛，是以被大家稱為大富翁世界的青春玉女掌門人。 舞美拉最近迷上了一款音樂遊戲。遊戲是這樣的，玩家要在規定時間内完成一首歌曲，歌曲共有N個音節，各個音節都有相應的分數。如果在相應音節按了對應的按鍵的話那麼就可以得到這個分數。比如某首歌曲，有5個音節，每個音節的分數是2,4,3,6,5。如果舞美拉正确得在第1,3,5個音節按鍵的話，那麼舞美拉可以得到的總分數是2+3+5=10分。 舞美拉雖然是個舞蹈很有天賦的人，但是在玩遊戲上手指就不是那麼靈敏了。她在正确完成一個音節之後至少要隔T個音節後才能正确完成下一個音節。現在舞美拉想知道，她能拿到的最大分數是多少？
Input
T<=10代表測試資料個數 對每組測試資料 第一行兩個整數N,T。N<=10000，代表歌曲的音節數，0<=T<=10在題目描述中提到過 然後是一行N個正整數，第i個整數代表正确完成第i個音節可以得到的分數，每個正整數<=100000000
Output
對每組測試資料，輸出舞美拉可以得到的最大分數，每組測試資料占一行。
Sample Input
25 12 4 3 6 55 02 4 3 6 5
Sample Output
1020
1：這題的狀态轉移方程是：f(x)=max(f(x-t-1)+w[x],max(f(x),f(x-1))); f(x-1)是代表沒有隔t+1選；
2：注意在t+1之前的f(x)=w(i);
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10005;
long long f[maxn];
long long w[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,t;
scanf("%d%d",&n,&t);
for(int i=0;i<n;i++)
scanf("%lld",&w[i]);
memset(f,0,sizeof(f));
for(int i=0;i<t+1;i++)
f[i]=w[i];
for(int v=0;v<n;v++){
if(v>0){
f[v]=max(f[v],f[v-1]);
if(v>=t+1)
f[v]=max(f[v],f[v-t-1]+w[v]);
}
}
long long mx=-1;
for(int i=0;i<n;i++)mx=max(mx,f[i]);
printf("%lld\n",mx);
}
return 0;
}