题目链接：https://codeforces.com/gym/102832/problem/A
题目大意：
用人民币（RMB）来兑换一种虚拟货币coupon，兑换规则如下：
共可以使用七种兑换方式，每种兑换方式第一次被使用时都会有额外奖励：
① RMB 1 → Coupon 10 额外奖励：8
② RMB 6 → Coupon 60 额外奖励：18
③ RMB 28 → Coupon 280 额外奖励：28
④ RMB 88 → Coupon 880 额外奖励：58
⑤ RMB 198 → Coupon 1980 额外奖励：128
⑥ RMB 328 → Coupon 3280 额外奖励：198
⑦ RMB 648 → Coupon 6480 额外奖励：388
现在要求用给定的钱兑换尽量多的Coupon，问能换到多少Coupon
分析：
很容易发现，如果不考虑额外奖励，那么RMB和Coupon 的兑换率就是1比10
而额外奖励只有第一次使用该兑换方式时才能得到，也就是最多得到一次
故转换为01背包问题
将兑换方式抽象为物品，每种物品的价值即为其额外奖励，费用如题所述
求给定容量的背包最多能装多少价值的物品
代码：
#include <cstdio>#include <iostream>#include <string.h>#include <algorithm>using namespace std;int main(){ int N; cin>>N; int value[8]={0,8,18,28,58,128,198,388}; int cost[8]={0,1,6,28,88,198,328,648}; int dp[10][2005]; memset(dp,0,sizeof(dp)); for(int i=1;i<8;i++) for(int j=1;j<=N;j++){ if(j>=cost[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+value[i]); else dp[i][j]=dp[i-1][j]; } cout<<N*10+dp[7][N]<<endl; return 0;}