TLE #9 #10:

//动态规划-二维
#include<iostream>
using namespace std;
const int N=1e4+5;  
int n,m,t[N],v[N];
int dp[N][N];
//dp[i][j]:在前i个物品中选择,并且它们的时间和为j,的价值的集合
//性质:max
//状态计算:
//不选:dp[i][j]=dp[i-1][j];
//选择:(1 2 3 k ...)
//     dp[i][j]=dp[i-1][j-k*t[i]]+k*v[i];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k*t[i]<=j;k++){
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*t[i]]+k*v[i]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

二维优化成一维后发现 WA #10:

//动态规划-一维
#include<iostream>
using namespace std;
const int N=1e7+5;  
int n,m,t[N],v[N];
int dp[N];
//dp[j]:在前n个物品中选择,并且它们的时间和为j,的价值的集合
//性质:max
//状态计算:
//不选:dp[j]=dp[j];
//选择:(1 2 3 k ...)
//     dp[j]=dp[j-t[i]]+v[i];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=t[i];j<=m;j++){
            dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

最后开了浪浪发现 AC:

//动态规划-一维
#include<iostream>
#define int long long
using namespace std;
const int N=1e7+5;  
int n,m,t[N],v[N];
int dp[N];
//dp[j]:在前n个物品中选择,并且它们的时间和为j,的价值的集合
//性质:max
//状态计算:
//不选:dp[j]=dp[j];
//选择:(1 2 3 k ...)
//     dp[j]=dp[j-t[i]]+v[i];
signed main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=t[i];j<=m;j++){
            dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}