hdu 2159 Fate （二维完全背包）

​​  输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个) 分析：

限制条件： 1.忍耐度 m   2.杀怪个数 s

构造： dp[m][s]   得到的经验值

（请不要读错题，不然老是给自己带来一种“为什么我写的程序就不对啊？"的感觉。红色字体。。。）

for(int i=0;itemp?dp[j][k]:temp; } }}

以上DP过程将完成二维的状态转移。当dp[i][j]>=n时，i表示能用i得到经验值，且经验值大于等于n。

#include #include #include #include using namespace std;const int N=105;int wei[N],val[N];int dp[N][N];int main(){ //freopen("cin.txt","r",stdin); int n,m,k,s; while(~scanf("%d%d%d%d",&n,&m,&k,&s)){ for(int i=0;itemp?dp[j][k]:temp; } } } bool tag=0; int ans=0; for(int i=1;i<=m;i++){ for(int j=s;j>=0;j--){ if(dp[i][j]>=n){ ans=i; tag=1; break; } } if(tag) break; } if(tag) printf("%d\n",m-ans); else printf("-1\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。