P3985 不开心的金明
-
这道题好像是01背包,但价格 \(v[i]\) 是 \(10^9\) 级别的,意味着dp数组的第一维要开到 \(10^9\),显然不可能
-
题目中说:
对所有的 \(i=1,2,3,…,N\),$ min(v_i) \le v_i \le min(v_i)+3$.
-
也就是 \(v[i]\) 的最大值最小值的差不大于3,由此想到把每个 \(v[i]\) 减去 \(v[i]_{min} -1\),再按照01背包去做
-
但是都减去一个数后无法通过一般的01背包的dp数组确定“考虑了前 \(i\) 件物品,总价为 \(j\)”中的 \(j\),所以要把状态表示改变一下
状态表示
\[dp[j][k]表示考虑了前i件物品后(包括当前物品),选了k件物品,减去 v[i]_{min}-1 后的总价为j \]- 所以转移方程如下
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e9;
int n,w;
int mini=INF,sum,maxi;
struct Obj{
int v,p;
}in[101];
int dp[1001][1001];
signed main(){
// freopen("1.in","r",stdin);
cin>>n>>w;
for(int i=1;i<=n;i++){
cin>>in[i].v>>in[i].p;
sum+=in[i].v;
mini=min(mini,in[i].v);
}
mini--;
sum-=mini*n;
for(int i=1;i<=n;i++)
in[i].v-=mini;
for(int i=1;i<=n;i++){
for(int j=sum;j>=in[i].v;j--){
for(int k=1;k<=n;k++){
if(j+mini*k<=w)
dp[j][k]=max(dp[j][k],dp[j-in[i].v][k-1]+in[i].p);
}
}
}
for(int i=1;i<=sum;i++){
for(int j=1;j<=n;j++)
maxi=max(maxi,dp[i][j]);
}
cout<<maxi<<"\n";
}
标签:开心,01,mini,P3985,sum,min,int,dp,金明
From: https://www.cnblogs.com/wangyangjena/p/17468249.html