题目类型 背包 | 对背包问题不了解的同学 猛戳 -> 背包九讲
题目意思
给出 n 件物品(1 <= n <= 2000)
每件物品有两个属性 Ti Ci (Ti 的意思是如果你取这件物品的话可以免费取其他的 Ti件物品 Ci的意思是如果你取这件物品需要花费Ci)
问 把 n 件物品取完需要的最少花费是多少
解题方法
dp[i][j] -> 取完前 i 件物品后还可以免费取 j 件物品的最小花费
状态转移
不取第i件物品 dp[i][j-1] = min(dp[i][j-1], dp[i-1][j] (因为取完前i-1个物品后如果还可以免费取其他j个物品的话 就可以把第i个物品取了变 成dp[i][j-1])
取第i件物品 dp[i][j+第i件物品可以提供的免费数] = min(dp[i][j+第i件物品可以提供的免费数], dp[i-1][j] + 第i件物品所需的花费)
递推即可
注意
j的下标可能是负数 所以可以所有下标向右移若干位
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2000 + 10;
typedef long long LL;
const LL INF = ((LL)1)<<62;
const int add = 2000;
int a[MAXN][2];
LL dp[MAXN][MAXN*2];
int main() {
int n;
while(scanf("%d", &n) != EOF) {
for( int i=0; i<n; i++ ) {
scanf("%d%d", &a[i][0], &a[i][1]);
}
for( int i=0; i<n; i++ ) for( int j=0; j<=4000; j++ ) dp[i][j] = INF;
dp[0][a[0][0]+add] = a[0][1];
dp[0][-1+add] = 0; //不选这件物品的话就意味着 取了这件物品还可以免费取 -1 件其他物品 加上add为了使下标不是负数,所有下标整体右移
for( int i=1; i<n; i++ ) {
for( int j=0; j<=4000; j++ ) {
if(j>0) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j]);
if(j+a[i][0]<=4000) dp[i][j+a[i][0]] = min(dp[i][j+a[i][0]], dp[i-1][j] + a[i][1]);
}
}
LL res = INF;
for( int i=add; i<=4000; i++ ) res = min(res, dp[n-1][i]); //从add开始即从0开始, 表示取完了n件物品后(下标从0开始所以是n-1)
cout<<res<<endl; //还可以取其他至少0件物品的最小值, 因为dp数组的第二维非负才有实际意义
}
return 0;
}