【算法每日一练]-动态规划 （保姆级教程 篇15）#动物 #赶deadline #page #构造字符串

目录

今日知识点：

01背包的路径输出

计算位和的数位dp

不用管字符串，只需要看好约束dp转移的变量

动物

?赶deadline

page?

构造字符串?

---

????????

????????

动物

有某类动物，可以在农场待n天，每天最多增加一只动物，第i天到来的动物每天要吃的粮食为c[i]，现在初始粮食是X，问在每天动物尽可能多的情况下最多容纳多少只动物？

输入：? ? ? ? ? ? ?输出：

3 4? ? ? ? ? ? ? ? ? ? ? ? 2

1 1 1

思路：

如果一直考虑每天的食量的话，这道题就不好做了。其实换个角度想一下：

动物来的时间是确定的，那么动物一共吃掉的食物也就确定了，那么者就转化成了01背包问题。

X是背包容量，每只动物的总食量是体积，价值就是1.

#include <bits/stdc++.h>
using namespace std;
int a[1005],f[100005],n,x;
int main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]*=(n-i+1);
	}
	for(int i=1;i<=n;i++)
	for(int j=x;j>=a[i];j--)
		f[j]=max(f[j],f[j-a[i]]+1);
	cout<<f[x];
}

????????

????????

?赶deadline

输入：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?输出：157
4 1000? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 3 4
50 500
75 400
60 300
22 200

?????????

?思路：

还是一道01背包。不过要输出路径，或者说输出拿到的物品。

举个例子把：

物品编号：? ? ? ?物品体积：? ? ? ?物品价值：

1 2 3 4? ? ? ? ? ? ? 2 3 4 5? ? ? ? ? ? ? 3 4 5 6

我们的背包转移情况如下图：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)

也就是说以蓝色格子为例：仅可以从正上方[1][3]或[1][0]转移过来（如图）。

那么也就是说那 如果f[2][3]和f[1][3]相等，说明没有拿第2个物品；否则就是拿了第2个物品，此时转移到f[1][3-w2]即f[1][0]。

????????

?那么整个回溯过程如下面的草图。

每个格子[i][j]都只有两种选择要么是(不拿这个物品)向上走[i-1][j]，要么是(拿这个物品) 走到f[i-1][j-w]。这样就能输出整个物品的装入情况了。

?

但是我的不是这么写的。因为是基于一维的背包。直接标记转移更新的就行，对于那些没有放入的物品，我们直接不去标记，这样也能直接找到回溯路径。（可以认为是上图中的取物品的为1，不取物品的为0）

? ? ? ?代码 部分：

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int t,n,w[N],v[N],f[N],pa[N][N],ans[N];
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>v[i]>>w[i];
	for(int i=1;i<=n;i++)
	for(int j=t;j>=w[i];j--)
		if(f[j-w[i]]+v[i]>f[j]){
			f[j]=f[j-w[i]]+v[i];
			pa[i][j]=1;
		}
	cout<<f[t]<<'\n';
	int i=n,j=t,cnt=0;
	while(i>=1&&j){
		if(pa[i][j]){
			ans[cnt++]=i;
			j-=w[i];
		}
		i--;
	}
	for(int k=cnt-1;k>=0;k--){
		cout<<ans[k]<<" ";
	}	
}

????????

? ? ? ?

page?

思路：

一道数位dp题。（卡了我好久）
和之前一样，我最开始定义的是f[3][2]代表200~299的数字。

然后转移方程:f[i][j]=f[i-1][0~9]+j*pow(10,i-1)，然后再求cal(n)的时候就发现不太好求了。

因为之前的cal过程是：

外层num[i]从高位到低位取数，里面0~num[i]-1全部加起来。然后逐渐发现不对劲……

最高位的数字一直在丢，没有加上去。导致结果不对。

最后，越写越丑，干脆不写了。

????????

正确做法是可以直接的定义f[3][2]代表000~299的数字。

计算f[i][j]的转移方程是这样的：

举个例子：0~7999 即f[4][7]。

f[4][7]=7*10^3+f[4][9]+f[4][0]即：

0~7999=7000+0~6999+0~0999

故：f[i][j]=j*10^(i-1)+f[i][j-1]+f[i][0]

然后求cal(n)：

求0~7213

0~7213=0~6999+7*214+0~213（对1000取模就行了）

0~213=0~199+2*14+0~13? ? ?（对100取模就行了）

0~13=0~9+1*4+0~3

外层num[i]从高位到低位取数，高位以下求和，然后计算高位数的次数，进入下循环。

终于结束了！！！！！！

????????
感悟就是：初始化的转移方程和最终求解cal(n)拆分方式的都至关重要。要亲自模拟一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll f[11][10];//f[i][j]表示数字长度为i且最大到以j开头的数字对应的答案数  eg：f[3][2]代表000~299的数字
void init(){
	for(int i=1;i<11;i++){
		f[i][0]=f[i-1][9];
		for(int j=1;j<=9;j++){
			f[i][j]=j*pow(10,i-1)+f[i][j-1]+f[i][0];
		}
	}
}


void cal(int x){
	vector<int>num;int y=x;
	while(x) num.push_back(x%10),x/=10;
	ll ans=0;
	for(int i=num.size()-1;i>=0;i--){
		int t=num[i];
		if(!t) continue;
		ans+=f[i+1][t-1]+(y%int(pow(10,i))+1)*t;
	}
	cout<<ans;
}
int main(){
	cin>>n;
	init();
	cal(n);
}

最后再说一下为什么这次换了这种定义方式：

因为这里不需要内这些内部的数进行处理。直接整体处理就行了。定义成f[i][j]表示i长度，j为最大开头的情况数； 但是之前的都是需要看开头数字的，所有只能定义成f[i][j]表示以i长度，j开始的数字的情况数。?

????????

????????

构造字符串?

用a，b，c来构造一个长n的字符串，要求：不能有连续三个相同的相邻，如aaa。问有多少种构造方法？

输入：
2
30
5000

思路：

初看还挺简单的，然后设置f[i][j]表示i长度，j结尾的方案数。然后还要考虑有几个相邻，开3维吗？

其实完全不用，a，b，c我们完全不需要管他们，只需要记录已经有几个相邻就行了。因为我们的转移仅仅受到相邻多少个相同的元素的约束。

那就直奔主题吧。设置f[i][1]表示长度i，结尾没有两个相同元素相邻；f[i][0]表示长度i，结尾有两个相同元素相邻；（哈哈哈，根本不存在有3个结尾相邻的情况，所以到0，1就足够了）

转移方程：f[i][0]=f[i-1][1]

f[i][1]=f[i-1][0]+f[f-1][1]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll x,n,f[100005][2];
int main(){
	f[1][0]=0;f[1][1]=3;
	for(int i=2;i<=100000;i++){
		f[i][0]=f[i-1][1];
		f[i][1]=2*(f[i-1][0]+f[i-1][1])%mod;
	}
	cin>>x;
	while(x--){
		cin>>n;
		cout<<(f[n][0]+f[n][1])%mod<<'\n';
	}
}