动态规划（一）

文章目录

• 1、建造房屋
• 2、破损的楼梯
• 3、可构造的序列总数
• 4、最快洗车时间
• 5、安全序列
• 6、地图
• 7、电影放映计划

1、建造房屋

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9+7;
int n,m,k; 
ll dp[50][5000];//前i个街道花了j元的方案数 dp[i][j] += dp[i-1][j-v] 
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m>>k;
	//因为有至少一个房屋的限制，所以我们先定一个位置
	ll o=m-1,h=k-n;// o 每个街道余下的位置，h 剩余的预算 
	for(ll i=0;i<=h;i++)dp[0][i]=1;// 剩余的预算 最多可以有几个位置 
	for(ll j=0;j<=n;j++)dp[j][0]=1;// 所有的街道起初都要有一个位置 
	
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=h;j++){
			if(j>i*o){
				dp[i][j]=dp[i][j-1];
				continue;
			}
			for(ll v=0;v<=j&&v<=o;v++)dp[i][j]=(dp[i][j]+dp[i-1][j-v])%p;
		}
	}
	cout<<dp[n][h];
	return 0;
}

2、破损的楼梯

#include<bits/stdc++.h>
using namespace std;
// dp[i] = dp[i-1] + dp[i-2]
using ll = long long;
const ll p = 1e9+7;
ll n,m,dp[100001],a[100001];
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int mm;cin>>mm;
		a[mm]=1;
	}
	dp[0]=1;
	if(!a[1])dp[1]=1;
	for(ll i=2;i<=n;i++){
		if(a[i])continue;
		dp[i]=(dp[i-1]+dp[i-2])%p;
	}
	cout<<dp[n];
	return 0;
}

3、可构造的序列总数

#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
const ll p = 1e9+7;                                 
ll dp[2005][2005];//dp[i][j]表示序列长度为 i，且以 j 结尾的合法序列的数量 
ll ans;
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int N,K;cin>>K>>N;
    for(int i=1;i<=K;i++)dp[1][i]=1;//只有1个数，无论是选择1~K中哪个数，都只有1种方案 
    
    for(int i=2;i<=N;i++){//2~N 遍历每一种序列长度
		for(int j=1;j<=K;j++){// 遍历当前序列中最后一个元数的每一种可能 
			for(int k=1;k*k<=j;k++){//遍历每一种可能是j的因子的取值
				if(k*k==j){//偶数，就一个因数  k 
					dp[i][j]=(dp[i][j]+dp[i-1][k])%p; 
				}else if(j%k==0){//说明有两个因数，j/k 和 k 
					dp[i][j]=(dp[i][j]+dp[i-1][j/k]+dp[i-1][k])%p; 
				}	
			}	
		} 
	}
    
    for(int i=1;i<=K;i++){//累加所有长度为N的以1~K结尾的序列数量 
    	ans=(ans+dp[N][i])%p;
	}
	cout<<ans;
    return 0;
}

4、最快洗车时间

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e4+5;
//dp[i][j] 表示前 i 辆车的洗车时间是否需要 j 时间(true or false) 
int tim[109];
bool dp[109][N];
ll n,sum,ans=N;
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>tim[i];
		sum=sum+tim[i];//一台机器洗车时间 
	}
	for(int i=0;i<=n;i++)dp[i][0]=true;
	
	for(int i=1;i<=n;i++){//遍历 n 辆车都可能的洗车时间
		for(int j=0;j<=sum;j++){//对于每一种洗车方案，遍历每一种可能的方案
			dp[i][j]=dp[i-1][j];
			if(j>=tim[i])dp[i][j]=dp[i][j]|dp[i-1][j-tim[i]];//选择洗 or 不洗 
		} 	
	} 
	
	for(ll i=1;i<=sum;i++){
		if(dp[n][i]){
			int tmp=max(sum-i,i);
			if(tmp<ans)ans=tmp;
		}
	}
	cout<<ans;
	return 0;
}

5、安全序列

#include<bits/stdc++.h>
using namespace std;
const int p = 1e9+7,N = 1e6+5;
int dp[N],prefix[N];//  dp[i] 表示以位置 i 结尾的方案总数 
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int n,k;cin>>n>>k;
	
	dp[0]=prefix[0]=1;
	for(int i=1;i<=n;i++){
		if(i-k-1<1)dp[i]=1;
		else dp[i]=prefix[i-k-1];
		prefix[i]=(prefix[i-1]+dp[i])%p;
	}
	cout<<prefix[n]<<'\n';
	return 0;
}

6、地图

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+3;
char mp[N][N];
int n,m,sk; 
int dp[105][105][2][7];//记忆化数组 
// dp[i][j][0][k] 表示从(i,j)开始，方向向下(1向上)，共改变了k次方向，到达终点的方案数量 
bool isnmp(int x,int y){
	return x>0&&x<=n&&y>0&&y<=m;
}
int dfs(int x,int y,int tag,int k){
	int cnt=0;
	if(!isnmp(x,y)||mp[x][y]=='#')return 0;
	if(x==n&&y==m)return 1;
	if(dp[x][y][tag][k])return dp[x][y][tag][k];
	
	if(k<sk){
		cnt=cnt+dfs(x+1,y,1,tag==1?k:k+1);//向下
		cnt=cnt+dfs(x,y+1,0,tag==0?k:k+1);//向右 
	}else if(k==sk){
		if(tag==0){
			cnt=cnt+dfs(x,y+1,tag,k);
		}
		if(tag==1){
			cnt=cnt+dfs(x+1,y,tag,k);
		}
	}
	return dp[x][y][tag][k]=cnt;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m>>sk;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	int ans=0;		
	ans=ans+dfs(1,2,0,0);
	ans=ans+dfs(2,1,1,0);
	cout<<ans;
	return 0;
}

7、电影放映计划

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5,M = 200;
int dp[N],m,n,t[M],w[M],k;
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++)cin>>t[i]>>w[i];
	cin>>k;
	m+=k;
	for(int i=1;i<=m;i++){
		dp[i]=dp[i-1];
		for(int j=0;j<n;j++){
			if(i>=t[j]+k){
				// dp[i]表示放映时间为i时的最大利润 
				dp[i]=max(dp[i],dp[i-t[j]-k]+w[j]);
			}
		}
	} 
	cout<<dp[m];
	return 0;
}