从数字三角形开始的DP生活——第二天

题目链接

#include<iostream>
#include<cstdio>
using namespace std;
const int N=105,M=1e3+5;
int n,m;
int f[N][M],v[N],w[N];
int ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=w[i]-1;~j;j--)
            f[i][j]=f[i-1][j];
        for(int j=m;j>=w[i];j--)
            f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
    }
        
    for(int i=1;i<=m;i++)ans=max(ans,f[n][i]);
    cout<<ans<<endl;
    return 0; 
}
//coder:Iictiw
//date:23/07/15

#include<iostream>
#include<cstdio>
using namespace std;
const int N=105,M=1e3+5;
int n,m;
int f[M],v[N],w[N];
int ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    for(int i=1;i<=m;i++)ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0; 
}
//coder:Iictiw
//date:23/07/15