题目描述
小明最近迷上了一款游戏，并且很想成为这款游戏的高手，这款游戏需要用
资源来买装备。他刚开始的资源价值为0,于是他每天都会做日常任务来获得价值为1的资源。
这款游戏中有每日商店，小明已经提前知道了接下来n天会出现的装备，每个装备都有一个价格 ai和他的强度值 bi，并且如果当天不买这件装备以后就买不到了。
但小明想要在这n天中买到强度总和最高的装备，你能帮助他吗?输入
第一行输入一个整数n代表天数。
接下来的n行每行两个整数ai和 bi,分别代表价格和强度值。输出
输出一个整数，表求小明能在这n天内获得的最大总强度值。
样例输入 Copy
【样例1】 4 1 1 2 2 3 3 4 4 【样例2】 5 2 100 1 2 2 10 3 20 2 1样例输出 Copy
【样例1】 4 【样例2】 22提示
对于样例一，小明会把资源都留到第四天时购买获得强度值为4的装备。
对于样例二，小明会买第二天的装备，并把第三天资源留下来买第四天的装备。
对于 30%的数据，保证1≤n≤20。
对于 50%的数据，保证1≤n≤ 300,并且 ai≤i的数量不超过 20。
对于 100%的数据，保证 1≤n,ai,bi≤5000。
是DP规划。搞不懂。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[6000],b[6000],dp[6000];
int main(){cin>>n;for(int i=1;i<=n;++i){cin>>a[i]>>b[i];}for(int i=1;i<=n;++i){for(int j=i;j>=a[i];--j){//买不起会跳过dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}}int ans=0;for(int i=1;i<=n;++i)ans=max(ans,dp[i]);cout<<ans;return 0;
}
