前言
一次简单的dp考试，但是由于审题错误 和 复杂度计算问题导致卡分……
详见下
1.打包
挺简单的一个01背包，就不详细写了。
2.暗黑破坏神
题面
思路
可以把每个药水转化成分组背包，但是重点就是对于无后效性的dp，如何记录前面的状态。
本来思路是先正常跑dp，将最大价值和最小花费求出，后用dfs跑满来找到这个方案。
但是dfs的复杂度计算错误，导致错误，只有45分……
后来也没有太好的解决办法，就改成每进行一次dp记录一下每个药水选了多少次吧……
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e2+5 , M = 5e2+5;
typedef long long ll;
typedef unsigned long long ull;
#define int ll
inline ll read(){
ll ret = 0 ; char ch = ' ' , c = getchar();
while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
while(c >= '0' && c <= '9')ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
return ch == '-' ? - ret : ret;
}
int n,m,p[M],w[N];
int c[N][N],sum,ans[M][M],dp[M][M];
signed main(){
n = read() , m = read();
for(int i = 1 ; i <= n ; i ++){
w[i] = read() , p[i] = read();
for(int j = 1 ; j <= p[i] ; j ++)
scanf("%lld",&c[i][j]);
}
for(int i = 1 ; i <= n ; i ++)
for(int j = m ; j >= w[i] ; j --)
for(int k = 1 ; k <= p[i] ; k ++){
if(j < k * w[i]) continue;
if(dp[j][0]<dp[j-k*w[i]][0]+c[i][k]){
dp[j][0]=dp[j-k*w[i]][0]+c[i][k];
dp[j][i]=k;
for(int h = i - 1 ; h >= 1 ; h --)
dp[j][h] = dp[j-k*w[i]][h];
}
if(dp[j - k * w[i]][0] + c[i][k] == dp[j][0]){
int s1 = 0 , s2 = 0;
for(int h = 1 ; h <= n ; h ++){
s1 += w[h] * dp[j][h];
}
s2 += k * w[i];
for(int h = i - 1 ; h >= 1 ; h --)
s2+=w[h]*dp[j-k*w[i]][h];
if(s2 < s1){
dp[j][i] = k;
for(int h = i - 1 ; h >= 1 ; h --)
dp[j][h] = dp[j-k*w[i]][h];
}
}
}
for(int i=0;i<=n;i++)
printf("%lld
",dp[m][i]);
return 0;
}
3.科技庄园
题面
思路
刚看题觉得好麻烦……
后来发现有用的信息：
- 总时间，总体力
- 每棵树的桃数
- 每棵树所耗的时间和体力
- 每棵树能摘的次数
再仔细想一下，可以转化成多重背包。
只需要总时间和总体力取(min)就是背包的大小
把每个有果子的树取出来，就变成了重量为(2 imes(i+j))的多重背包。
注意的是：他不想摘很多的桃以至体力为0，说明体力需要-1！
卡分就是因为这个问题！
另外，地图给的范围是(100*100)，所以要开背包大小为(100^2 *log(100)!)RE来源
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e2+5 , M = 1e4+5;
typedef long long ll;
typedef unsigned long long ull;
#define int ll
inline ll read(){
ll ret = 0 ; char ch = ' ' , c = getchar();
while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
while(c >= '0' && c <= '9')ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
return ch == '-' ? - ret : ret;
}
int n,m,V,w[M<<8],v[M<<8],dp[N],cnt;
signed a[N][N],b[N][N];
signed main(){
int x,y;
n = read() , m = read() , x = read() , y = read()-1;
V = min(x,y);
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
a[i][j] = read();
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++){
x = read();
for(int k = 1 ; k <= x ; k <<= 1)
w[++cnt] = k * (i+j)*2 , v[cnt] = k * a[i][j] , x -= k;
if(x)
w[++cnt] = x * (i+j)*2 , v[cnt] = x * a[i][j];
}
// for(int i = 1 ; i <= cnt ; i ++)
// printf("%lld:%lld %lld
",i,w[i],v[i]);
for(int i = 1 ; i <= cnt ; i ++)
for(int j = V ; j >= w[i] ; j --)
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
printf("%lld",dp[V]);
return 0;
}
4.金明的预算方案
题面
思路
还是一道经典题啦……因为一次A了就不详细写了。
对于每个主件，最多有2个附件，因此在01背包的时候增加为：
- 只选择当前主件
- 选择当前主件和第1个附件
- 选择当前主件和第2个附件
- 选择当前主件和第1、2个附件
于是把dp的地方略微修改就可以了
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 3.2e4+5 , M = 1e2+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret = 0 ;char ch = ' ' , c = getchar();
while(!(c >= '0' && c <= '9'))ch = c , c = getchar();
while(c >= '0' && c <= '9')ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
return ch == '-' ? -ret : ret;
}
int n,m;
int w[M],v[M],ma[M][3],cnt,cntm,wa[M],va[M];
int dp[N],to[N];
signed main(){
n = read() , m = read();
int a,b,c;
for(int i = 1 ; i <= m ; i ++){
a = read() , b = read() , c = read();
if(!c)
to[i] = ++cnt,w[cnt] = a, v[cnt] = b * a;
else
ma[to[c]][ ++ma[to[c]][0] ] = ++cntm , wa[cntm] = a , va[cntm] = b * a;
}
for(int i = 1 ; i <= cnt ; i ++){
for(int j = n ; j >= w[i] ; j --){
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
if(j >= w[i] + wa[ma[i][1]])
dp[j] = max(dp[j],dp[j-w[i]-wa[ma[i][1]]] + v[i] + va[ma[i][1]]);
if(j >= w[i] + wa[ma[i][2]])
dp[j] = max(dp[j],dp[j-w[i]-wa[ma[i][2]]] + v[i] + va[ma[i][2]]);
if(j >= w[i] + wa[ma[i][1]] + wa[ma[i][2]])
dp[j] = max(dp[j],dp[j-w[i]-wa[ma[i][1]]-wa[ma[i][2]]] + v[i] + va[ma[i][1]] + va[ma[i][2]]);
}
}
int ans = -INF;
for(int i = 0 ; i <= n ; i ++)
ans = max(ans,dp[i]);
// printf("%d:%d
",i,dp[i]);
printf("%d",ans);
return 0;
}