原题:http://acm.hdu.edu.cn/showproblem.php?pid=2182

总之很简单的题目，题目大意是给出N个点，每次移动的距离在A，B之间，移动次数不超过K，最终输出访问过的点之和的最大值。
先是用了dfs写了一遍，但是wa了，也查不出哪里有错。

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=101;
int T,N,A,B,K,res,tem,steps;
int ins[MAXN],vis[MAXN][MAXN];
void dfs(int start)
{
    if(steps==K)
    {
        res=res>tem?res:tem;
        return;
    }
    for(int i=A;i<=B;i++)
    {
        if(start+i<n)
        {
            tem+=ins[start+i];
            steps++;
            if(tem>vis[start+i][steps])
            {
                vis[start+i][steps]=tem;
                dfs(start+i);
            }
            steps--;
            tem-=ins[start+i];
        }
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        cin>>N>>A>>B>>K;
        for(int i=0;i!=N;i++)
            cin>>ins[i];
        res=0;
        tem=ins[0];
        steps=0;
        dfs(0);
        cout<<res<<endl;
    }
}

最后用了bfs过得。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct point
{
    int pos,num,steps;
};
const int MAXN=201;
int ins[MAXN],vis[MAXN][MAXN];
int T,N,A,B,K,res;
void bfs()
{
    queue<point> q;
    point cur,next;
    cur.pos=0;
    cur.num=ins[0];
    cur.steps=0;
    q.push(cur);
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
    //  if(cur.steps==K)
        if(cur.steps==K||cur.pos>=N)
        {
            res=res>cur.num?res:cur.num;
            continue;
        }
        for(int i=A;i<=B;i++)
        {
            next=cur;
            next.pos+=i;
            next.num+=ins[next.pos];
            next.steps++;
            if(vis[next.pos][next.steps]<next.num)
            {
                q.push(next);
                vis[next.pos][next.steps]=next.num;
            }
        }
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(ins,0,sizeof(ins));//这道题测试用例很迷，把这两条memset写在while外面也能ac
        cin>>N>>A>>B>>K;
        for(int i=0;i!=N;i++)
            cin>>ins[i];
        res=0;
        bfs();
        cout<<res<<endl;
    }
}