目录
今日知识点：
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';
}
}
