动态规划(Week8)

发布于 2022-12-26  101 次阅读


T1 疯狂的采药

题目:

是经典的01背包问题,在博客另一处有介绍,推出 状态转移方程即可。

代码如下。

#include <iostream>
using namespace std;
long long int T,n;
long long int t[10005],w[10005];
long long int dp[10000005];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++) 
	cin>>t[i]>>w[i];
	for(int i=1;i<=n;i++){
		for(int l=1;l<=T;l++){
			if(l>=t[i])
			dp[l]=max(dp[l],dp[l-t[i]]+w[i]);
		}
	}
	cout<<dp[T];
	return 0;
}

T2 摆花

题目:

计数dp

用填表法的思想可以得出更新dp数组的式子。

#include <iostream>
using namespace std;
const long long int x=1000007;
long long int n,m,a[104],dp[105][105];
//dp[i][j]记录有i种花,要摆j盆时的摆法。
int main(){
	dp[0][0]=1;//一种花都没有的话是一种情况。
	cin>>n>>m;
	for(long long int i=1;i<=n;i++)
	cin>>a[i];
	for(long long int i=1;i<=n;i++){
		for(long long int l=0;l<=m;l++){
			for(long long int p=0;p<=min(l,a[i]);p++){
				dp[i][l]=(dp[i][l]+dp[i-1][l-p])%x;//每次都取模。
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

T3 樱花

题目:

看题可以知道有些美学值是可以拿很多甚至无限次的,所以这是一个多重背包问题,可以用二进制优化将复杂度由O(n^3)优化至O(n^2 logn)

可以把没有次数限制的美学值次数设成一个比较大的数。

代码如下。

#include <bits/stdc++.h>
using namespace std;
int N,V;
int v[100000005],w[100000006],dp[100000005];
long long int hs,ms,he,me;
int main(){
	scanf("%lld:%lld %lld:%lld %lld",&hs,&ms,&he,&me,&N);
	he-=hs;
	if(me-ms<0)
	me=me-ms+60,he--,me+=he*60;
	else me = me - ms + he * 60;
	V=me;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS)
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		if(c==0) c=9999999;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=z*k;
			w[count]=x*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=z*c;
			w[count]=x*c;
		}
	}
	for(int i=1;i<=count;++i){
		for(int k=V;k>=0;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

T4 金明的预算方案

题目:

这题存附件数据技巧是开二维数组cost[x][y],x为第x件物品,当y为0时为这件物品本身,y为1时为第x件物品的附件1,y为2时为第x件物品的附件2。

然后每次选择有五种情况,

①只买主件
②买主件+附件1
③买主件+附件2
④买主件+附件1+附件2
⑤不买主件。

除了1和5冲突外,其他四个都能判断后更新新的dp值,顺序任意,枚举这五种情况,填表即可。

代码如下。

#include <iostream>
#include <cstring>
using namespace std;
int m,n;
int dp[70][40000];
int cost[70][5],imp[70][5];
int main(){
	cin>>m>>n;
	int c,im,f;
	for(int i=1;i<=n;i++){
		cin>>c>>im>>f;
		if(!f){
			cost[i][0]=c;
			imp[i][0]=im;
		}
		else{
			if(!cost[f][1]){
				cost[f][1]=c;
				imp[f][1]=im;
			}
			else{
				cost[f][2]=c;
				imp[f][2]=im;
			}
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(l-cost[i][0]>=0){
				dp[i][l]=max(dp[i-1][l],dp[i-1][l-cost[i][0]]+cost[i][0]*imp[i][0]);
				if(l-cost[i][0]-cost[i][1]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]);
				}
				if(l-cost[i][0]-cost[i][2]>=0){
				dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][2]*imp[i][2]);
				}
				if(l-cost[i][0]-cost[i][1]-cost[i][2]>=0){
					dp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]+cost[i][2]*imp[i][2]);
				}
			}
			else
			dp[i][l]=dp[i-1][l];
		}
	}
	cout<<dp[n][m];
	return 0;
}

总结:

记忆化搜索>dp?)。
代码写的好丑呀。(不是什么大问题就是)