D. 百里传送
Problem ID: 7340
Contest ID: 6577
必做题
Memory Limit Exceeded
题目描述
给定 n 个整数 a1…an。
有 n+1 个位置：0, 1, 2, …, n。
你初始时在 0 位置，每次你可以选择以下其中一种操作：
- 向右移动一格，代价为 1。
- 向左移动一格，代价为 1。
- 传送回 0 位置，记你当前的位置为 i，则传送的代价为 ai。注意：每个位置只能发动一次传送。也就是说，若你某次在 i 处发动传送，则在此之后到达 i 位置时不能选择传送操作。
问总代价不超过 c 时，最多能发动几次传送。
输入格式
第一行一个整数 T 代表数据组数。
每组数据第一行两个整数代表 n 和 c，第二行 n 个数表示 a1 到 an。
输出格式
每组数据输出一行，代表答案。
样例输入
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
样例输出
2
2
0
1
2
2
1
1
1
2
数据规模
1\leq T\leq 1000,1\leq n\leq2\times10^5,1\leq c,a_i\leq 10^9,\sum n\leq2\times10^5
我的代码：
#include <bits/stdc++.h>
using namespace std;
int q,n,m,a[200200],ans;
bool b[200200];
int dx[]={-1,1};
void init()
{
memset(b,0,sizeof(b));
ans=0;
}
void dfs(int x,int s,int num)
{
if(s>=m)
{
ans=max(ans,num);
return;
}
for(int i=0;i<2;i++)
{
int p=x+dx[i];
if(p>=0 && p<=n)
{
dfs(p,s+1,num);
if(!b[p] && p)b[p]=true,dfs(0,s+a[p],num+1),b[p]=false;
}
}
}
int main()
{
cin>>q;
while(q--)
{
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
dfs(0,0,0);
printf("%d\n",ans);
}
return 0;
}
不会求教！
