P1802 5倍经验日

admin

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

这是一个基本背包问题的变形，一般的背包在不选择此物的时候不改变上一次的重量和价值，而此题在不使用药物的时候还可以得到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. }
    
30. 
    

复制代码

要是用一维数组就得有些技巧了。不同套用以前的那种写法。

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. }
    
24. 
    

复制代码

黄煦喆

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尧

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. }
    

复制代码