题目描述
正在入侵艾泽拉斯的古尔丹偶然间得到了一颗邪能炸弹，经过研究，他发现这是一颗威力极其巨大且难以控制的炸弹。但是精通邪能的古尔丹突然有了一个大胆的想法，他对炸弹进行了一些小小的改造。这使得炸弹需要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天炸弹可能达到的最大邪能值，如果炸弹无法避免邪能值低于0或者高于MAX则输出-1。 样例输入
2 3 5 10 5 3 7
3 3 8 5 2 10 样例输出
10 -1 提示
dfs 暴力就不用说了 。 代码
#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 1000+10; const int MAXM = 1e5; int L,R; int minval; int arr[100]; int n; void dfs(int now,int sum,int id){ if(sum>R||sum<L) return; if(id==n) { minval=max(minval,sum); return ;} dfs(now+1,sum+arr[now+1],id+1); dfs(now+1,sum-arr[now+1],id+1); } int main(){ int t ;cin>>t; while(t--){ int st,maxx; scanf("%d%d%d",&n,&st,&maxx);int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&arr[i]); sum+=arr[i]; } if(sum<maxx) printf("%d\n",sum); else{ L=0;R=maxx;minval=0; dfs(0,st,0); if(minval==0) puts("-1"); else printf("%d\n",minval); } } return 0; }第二种解法： DP。设状态dp [ i ] [ j ] 表明第 i 天 能量为 j 的情况 0代表无法到达1代表可以到达 。 代码
#include<bits/stdc++.h> using namespace std; #define LL long long const int MAXN = 100; const int MAXM = 1e4+11 ; const int inf = 0x3f3f3f3f; const int mod = 1e9+7 ; int dp[MAXN][MAXM]; int x[MAXN]; int main(){ int T ;cin>>T; while(T--){ int n,st,upper;cin>>n>>st>>upper; for(int i=1;i<=n;i++) cin>>x[i]; memset(dp,0,sizeof(dp)); dp[0][st]=1; for(int i=1;i<=n;i++){ // 由第i-1天的状态 可以推出来第i天可能到达的所有位置。 for(int j=0;j<=upper;j++) { if(j>=x[i]&&dp[i-1][j-x[i]]==1) dp[i][j]=1; if(dp[i-1][j+x[i]]==1) dp[i][j]=1; } } int ans=-1; for(int j=0;j<=upper;j++) if(dp[n][j]==1) ans=max(ans,j); cout<<ans<<endl; } return 0 ; }