华师一附中OI组

标题: P1802 5倍经验日 [打印本页]
作者: admin    时间: 2018-10-14 10:42
标题: P1802 5倍经验日
https://www.luogu.org/problemnew/show/P1802

题目背景
现在乐斗有活动了！每打一个人可以获得5倍经验！absi2011却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

题目描述
现在absi2011拿出了x个迷你装药物(嗑药打人可耻….)，准备开始与那些人打了

由于迷你装一个只能管一次，所以absi2011要谨慎的使用这些药，悲剧的是，没到达最少打败该人所用的属性药了他打人必输>.<所以他用2个药去打别人，别人却表明3个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有n个好友，有输掉拿的经验、赢了拿的经验、要嗑几个药才能打过。求出最大经验（注意，最后要乘以5）

输入输出格式
输入格式：
第一行两个数，n和x

后面n行每行三个数，分别表示输了拿到的经验(lose(i))、赢了拿到的经验(win(i))、打过要至少使用的药数量(use(i))。

输出格式：
一个整数，最多获得的经验

输入输出样例
输入样例#1：
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
输出样例#1：
1060
说明
【Hint】

五倍经验活动的时候，absi2011总是吃体力药水而不是这种属性药>.<

【数据范围】

对于10%的数据，保证x=0

对于30%的数据，保证n<=10,x<=20

对于60%的数据，保证n<=100,x<=100, 10<=lose(i), win(i)<=100,use(i)<=5

对于100%的数据，保证n<=1000,x<=1000,0<lose(i)<=win(i)<=1000000,0<=use(i)<=1000

作者: admin    时间: 2018-10-14 11:47
这是一个基本背包问题的变形，一般的背包在不选择此物的时候不改变上一次的重量和价值，而此题在不使用药物的时候还可以得到lose的值，所以转移方恒也有所不同。
基本的二位数组的做法，很直观
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4. const int mx=1100;
  5. const int mn=1100;
  6. long long f[mn][mx];
  7. int win[mn],lose[mn],use[mn];
  8. int n,x,r,c,i;
  9. long long t1,t2;
  10. int main()
  11. {
  12.     cin>>n>>x;
  13.     for (i=1; i<=n; i++)  cin>>lose[i]>>win[i]>>use[i];
  14.     for(r=1; r<=n; r++)
  15.         for(c=0; c<=x; c++)
  16.         {
  17.             t1=f[r-1][c]+lose[r];
  18.             if (c>=use[r]) t2=f[r-1][c-use[r]]+win[r];else t2=0;
  19.             f[r][c]=max(t1,t2);
  20.         }
  21.     /*for(r=1; r<=n; r++)
  22.     {
  23.         for(c=0; c<=mj-1; c++)  cout<<setw(4)<<f[r][c];
  24.         cout<<endl;
  25.     }
  26.     */
  27.     cout<<5*f[n][x];
  28.     return 0;
  29. }

复制代码


要是用一维数组就得有些技巧了。不同套用以前的那种写法。
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4. const int mn=1100;
  5. long long f[1100];
  6. int win[mn],lose[mn],use[mn];
  7. int n,x,r,c,i;
  8. long long t1,t2;
  9. int main()
  10. {
  11.     cin>>n>>x;
  12.     for (i=1; i<=n; i++)  cin>>lose[i]>>win[i]>>use[i];
  13.     for (r=1; r<=n; r++)
  14.         for(c=x; c>=0; c--)
  15.         {
  16.             t1=f[c]+lose[r];
  17.             if (c>=use[r]) t2=f[c-use[r]]+win[r];
  18.             else t2=0;
  19.             f[c]=max(t1,t2);
  20.         }
  21.     cout<<5*f[x];
  22.     return 0;
  23. }

复制代码
作者: 黄煦喆    时间: 2018-10-14 22:14
  1. #include<iostream>
  2. using namespace std;
  3. int n,x;
  4. int w[1001],l[1001],use[1001];
  5. long long f[1001];
  6. int main()
  7. {
  8.     cin>>n>>x;
  9.     for(int i=1;i<=n;i++)
  10.     {
  11.         cin>>l[i]>>w[i]>>use[i];
  12.         for(int j=x;j>=use[i];j--)f[j]=max(f[j]+l[i],f[j-use[i]]+w[i]);
  13.         for(int j=0;j<use[i];j++)f[j]+=l[i];///注意这里是0起步
  14.     }
  15.     cout<<f[x]*5;
  16.     return 0;
  17. }
复制代码
作者: type尧    时间: 2018-11-4 18:59
  1. //
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<algorithm>
  6. #define maxium 1010
  7. using namespace std;
  8. typedef long long ll;
  9. struct node{
  10.         int need,win,lose;
  11. }fri[maxium];
  12. ll n,x,ans;
  13. ll f[maxium][maxium];
  14. void read()
  15. {
  16.         cin>>n>>x;
  17.         for(int i=1;i<=n;i++)
  18.                 cin>>fri[i].lose>>fri[i].win>>fri[i].need;
  19.         return;
  20. }
  21. void dp()
  22. {
  23.         read();
  24.         for(int i=1;i<=n;i++)
  25.                 for(int j=x;j>=0;j--)
  26.                         if(j>=fri[i].need) f[i][j]=max(f[i-1][j]+fri[i].lose,f[i-1][j-fri[i].need]+fri[i].win);
  27.                                 else f[i][j]=f[i-1][j]+fri[i].lose;
  28.         cout<<f[n][x]*5;
  29.         return;
  30. }
  31. int main()
  32. {
  33.         dp();
  34.         return 0;
  35. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2