柱爷与咸鱼神功

Time Limit: 1000/1000MS (Java/Others)     Memory Limit: 120000/120000KB (Java/Others)

Submit  Status

某日，喵哈哈村，柱爷在自己房间内，面对魔镜

"魔镜啊，魔镜，什么才是这个世界上最强大的武功？"

霎时，一道惊雷落下，柱爷的面前竟然浮现出了一本古老的黑色书籍，而书的名字竟然是 “咸鱼神功” “咸鱼神功”!

翻开一看，书的第一页赫然写着：” 练至大成可变身咸鱼王，掌控雷电！ 练至大成可变身咸鱼王，掌控雷电！“

看到这句话，柱爷当即决定修炼咸鱼神功！

既然是神功，也不是那么好练的，因此柱爷决定好好的规划一下自己的修炼过程！

柱爷有 N N点心情值，而咸鱼神功则有 M M个招式，对于每个招式，柱爷必须要消耗 Ti Ti点心情值才能掌握，同时柱爷会获得 Vi Vi的修炼值

那么，柱爷能够获得的最大修炼值是多少呢？

Input

第一行两个整数 N N, M M，分别表示柱爷的心情点数和咸鱼神功的招式数量

接下来 M M行，每行 2 2个整数， Ti，Vi Ti，Vi，分别表示学习该招式的消耗和能获得的修炼值

数据保证:

1≤N，M≤5000 1≤N，M≤5000

1≤Ti，Vi≤10000 1≤Ti，Vi≤10000

Output

输出仅一行，表示柱爷能获得的最大修炼值

Sample input and output

Sample Input Sample Output 5 4 2 5 2 3 3 9 4 4 14

Source

2016 UESTC Training for Dynamic Programming

题解：就是一个裸01背包

代码如下

#include <iostream> #include <bits/stdc++.h> using namespace std; int n; int w1; int v[10005]; int w[10005]; int dp[5005][5005]; int rec(int i,int j) { int res; if(dp[i][j]>=0) return dp[i][j]; if(i==n+1) res=0; else if(j<w[i]) res=rec(i+1,j); else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); return dp[i][j]=res; } int main() { cin>>w1>>n; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; for(int i=0;i<=n;i++) for(int j=0;j<=w1;j++) dp[i][j]=-1; //memset(dp,-1,sizeof(dp)); int ans=rec(0,w1); cout <<ans<< endl; return 0; }