【多校连萌2】1281: 邪能炸弹【补题】
题目描述
正在入侵艾泽拉斯的古尔丹偶然间得到了一颗邪能炸弹，经过研究，他发现这是一颗威力极其巨大且难以控制的炸弹。但是精通邪能的古尔丹突然有了一个大胆的想法，他对炸弹进行了一些小小的改造。这使得炸弹需要n天的充能才能爆炸，在这n天中，每天炸弹的邪能值都会产生波动，波动值为xi，古尔丹唯一能控制的是使邪能值增加xi或减少xi，如果邪能值小于0或大于MAX，那么炸弹将会损坏并失效。机智如古尔丹当然会做出最优选择。而作为反抗军的情报人员，你知道炸弹的初始邪能值为begin，寿命为n天以及每天的波动值xi。你需要知道在第n天炸弹可能达到的最大邪能值。
输入
第一行为一个整数T，表示有T组测试实例。
对于测试实例：
第一行为三个整数 n，begin，MAX。1<=n<=50,0<=begin<=MAX,1<=MAX<=1000。
第二行一次为n个整数 x1,x2,x3,x4...xn。1<=xi<=1000
对于测试实例：
第一行为三个整数 n，begin，MAX。1<=n<=50,0<=begin<=MAX,1<=MAX<=1000。
第二行一次为n个整数 x1,x2,x3,x4...xn。1<=xi<=1000
输出
对于每组测试实例输出一行，表示第n天炸弹可能达到的最大邪能值，如果炸弹无法避免邪能值低于0或者高于MAX则输出-1。
样例输入
2
3 5 10
5 3 7
3 3 8
5 2 10
样例输出
10
-1
思路：dp题， 用一个二维数组下标去记录第n天的最大邪能值，到达状态时则标记为1，从第i-1天推第i天时，第i-1天必须到达状态，用一个标志变量flag进行标记是否输出-1.如果在0-max都无法找到第i天能够到达状态的值，则终止循环。输出-1.
尽管get到了题解，还是wrong了5遍，原因在于自己忽略了退出循环的条件是0-max都无法找到符合条件的值，而不是一找到不符合条件的值就退出循环。
这道题吧，让我心情复杂，zzq没A的题，我果然也不能A
#include<stdio.h>
#include<string.h>
#define N 55
int num[N],dp[N][N*N];
int main()
{
int t;
int n,begain,max;
int i,j,flag;
scanf("%d",&t);
while( t --)
{
scanf("%d%d%d",&n,&begain,&max);
for(i = 1; i <= n; i ++)
scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
dp[0][begain] = 1;
for(i = 1; i <= n; i ++)
{
flag = 0;
for(j = 0; j <= max; j ++)
{
if(dp[i-1][j])
{
if(j-num[i]>=0)
{
dp[i][j-num[i]] = 1;
flag = 1;
}
if(j+num[i]<=max)
{
dp[i][j+num[i]] = 1;
flag = 1;
}
}
}
if(!flag)
break;
}
if(!flag)
printf("-1
");
else
{
for(i = max; i >= 0;i--)
{
if(dp[n][i])
{
printf("%d
",i);
break;
}
}
}
}
return 0;
}