P2722 [USACO3.1] 总分 Score Inflation

liu_zheng · 2025-02-06 16:38:11 · 个人记录

#include<bits/stdc++.h>
using namespace std;
/*
由于此题数据大 不能二维dp 滚动数组 
1.确定状态 dp[i][j]表示前面i种物品容量为j时能装的最大价值
2.确定答案 dp[n][m]
3.状态转移方程 
不装或装不下 dp[i]=pre[i]
装得下 dp[j]=dp[j-t[i]]+p[i]
4.初始值
dp[0][j]=0; 
*/
int n,m;
int p[10005],t[10005];
int dp[10005];
int pre[10005];
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i]>>t[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[j]=pre[j];
            if(j>=t[i]){
                dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
            }
        } 
        for(int j=0;j<=m;j++){
            pre[j]=dp[j];
        }
    }
    cout<<dp[m];
    return 0;
}