3121 - 学姐又去谷歌
学姐又要去Google上班了，这一次学姐想多做几道水题，并使题目的总水量最大.学姐同一时刻只能在水一道题，只有做完这道题才能得到它的水值，学姐的总时间为t，现在一共有n道题，编号从1到n，每道题有两个值a和b，a为做这道题需要的时间，b为题目的水值。
Input
数据中第一行为两个数t和n，n为题目的数量，t为总时间,接下来n行,每行两个正整数a和b。(1≤a,t≤1000，1≤n≤100，1≤b≤1000000)
Output
输出对应的最大总水量。
Examples
Input
10 2 8 16 6 12
Output
16
Solution C++
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; const int N=111111; long long w[N]; long long v[N]; long long dp[1111]; int main() { long long T,t,n; memset(dp,0,sizeof(dp)); cin>>t>>n; //cout<<"n::"<<t<<endl; for(long long i=0;i<n;i++) { cin>>w[i]>>v[i]; } for(long long i=0;i<n;i++) { for(long long j=t;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout<<dp[t]<<'\n'; return 0; }