额。果然是动(dou)态(bu)规(hui)划(zuo)专场。。。
A: 翻倍序列
dp[i][j]表示第i个位置是j的情况的个数
那么dp[i][j]=∑dp[i-1][k] (j%k==0)
初始状态下dp[0][j]=1。（1<=j<=n）
最后要求的答案是∑dp[n-1][i] （1<=i<=n）
可以先预处理好所有答案，然后询问的时候直接求和输出。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
int dp[][];
const int MOD=;
int main()
{
int n,k,i,j,kk;
n=,k=;
for(j=;j<=n;j++) dp[][j]=;
for(i=;i<k-;i++){
for(j=;j<=n;j++){
for(kk=j;kk<=n;kk+=j){
dp[i+][kk]=(dp[i+][kk]+dp[i][j])%MOD;
}
}
}
while(scanf("%d%d",&n,&k)!=EOF) {
int ans=;
for(j=;j<=n;j++){
ans=(ans+dp[k-][j])%MOD;
}
printf("%d\n",ans);
}
return ;
}
B: 汉诺塔
dp[k][i][j]表示把k个盘子从i移动到j所需要的最小花费。
首先z=3-i-j，表示除了i和j的另一个柱子
那么移动的时候有2种情况：
1.先把k-1个从i移动到z，然后把最大的那个从i移动到j，最后把z-1个从k移动到j
也就是dp[k][i][j]=dp[k-1][i][z]+cost[i][j]+dp[k-1][z][j]
2.先把k-1个从i移动到j，然后把最大的那个从i移动到z，之后把k-1个从j移动回i，再把最大的从z移动到j，最后k-1个从i移动到j
也就是dp[k][i][j]=dp[k-1][i][j]+cost[i][z]+dp[k-1][j][i]+cost[z][j]+dp[k-1][i][j]
然后两者取较小值。
最后要注意的是dp[0][i][j]=min{cost[i][j] , cost[i][z]+cost[z][j]}
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
int cost[][];
ll DP[][][];
ll dfs(int n,int i,int j){
//printf("%d %d %d\n",n,i,j);
int k=-i-j;
if(n==) return min(cost[i][j],cost[i][k]+cost[k][j]);
if(DP[n][i][j]!=-){
return DP[n][i][j];
}
ll ans1=;
ans1=dfs(n-,i,k);
ans1+=cost[i][j];
ans1+=dfs(n-,k,j); ll ans2=;
ans2=dfs(n-,i,j);
ans2+=cost[i][k];
ans2+=dfs(n-,j,i);
ans2+=cost[k][j];
ans2+=dfs(n-,i,j); return DP[n][i][j]=min(ans1,ans2);
}
int main()
{
int n;
while(scanf("%d%d%d",&cost[][],&cost[][],&cost[][])!=EOF)
{
memset(DP,-,sizeof(DP));
scanf("%d%d%d",&cost[][],&cost[][],&cost[][]);
scanf("%d%d%d",&cost[][],&cost[][],&cost[][]);
scanf("%d",&n);
printf("%lld\n",dfs(n,,));
}
return ;
}
C: 红黑树
dp[i][0]表示有i个节点的树，如果根节点是黑色，有几种构造。
dp[i][1]表示有i个节点的树，如果根节点是红色，有几种构造。
根据题意可知，最后要求的就是dp[n][0]的值（根节点必须是是黑色）
dp[i][0]= dp[i/2+i%2][0]*dp[i/2][0]
+dp[i/2+i%2][0]*dp[i/2][1]
+dp[i/2+i%2][1]*dp[i/2][0]
+dp[i/2+i%2][1]*dp[i/2][1]
dp[i][1]= dp[i/2+i%2][0]*dp[i/2][0]
dp[1][0]=1
dp[1][1]=0 (叶子节点不能是红色)
dp[2][1]=dp[2][0]=1
然后递推就行了。。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
const ll MOD=;
ll DP[][];
ll dfs(int x,int c)//x个节点，根节点颜色是c（0黑 1红）
{
//if(x<0) return 0;
if(x==&&c==) return ;//叶子节点不能是红色
if(x==) return ;//叶子节点是黑色
if(DP[x][c]!=) return DP[x][c];
ll ret=,l,r;
if((x-)%) l=(x-)/+;
else l=(x-)/;
r=(x-)/;
if(!c){//黑色
if(r!=){
ret=(ret+(dfs(l,)*dfs(r,))%MOD)%MOD;
ret=(ret+(dfs(l,)*dfs(r,))%MOD)%MOD;
ret=(ret+(dfs(l,)*dfs(r,))%MOD)%MOD;
ret=(ret+dfs(l,)*dfs(r,)%MOD)%MOD;
}else{ret=;}
}else{
if(r!=){
ret=(ret+dfs(l,)*dfs(r,)%MOD)%MOD;
}else{ret=;}
}
return DP[x][c]=ret;
}
int main()
{
int n;
memset(DP,,sizeof(DP));
while(scanf("%d",&n)!=EOF){
printf("%lld\n",dfs(n,));
}
return ;
}
D: 01序列
dp[i][0]表示前i个字符组成的的子序列中 以0为结尾的01序列
dp[i][1]表示前i个字符组成的的子序列中 以1为结尾的01序列
dp[i][0]=dp[i-1][1]+1 dp[i][1]=dp[i-1][1] (s[i]==0)
dp[i][1]=dp[i-1][0]+1 dp[i][0]=dp[i-1][0] (s[i]==1)
把全部加起来就是答案了。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
int main()
{
int n,i;
int MOD=;
while(scanf("%d",&n)!=EOF){
ll ans=;
ll a0=,a1=;
for(i=;i<n;i++){
if(i%){
ans=(ans+(a0+))%MOD;
a1=(a1+a0+)%MOD;
}else{
ans=(ans+(a1+))%MOD;
a0=(a0+a1+)%MOD;
}
}
printf("%lld\n",ans);
}
return ;
}
E: 矩阵的最长不降子串
dp[i][j]表示以a[i][j]结尾的不递减子串最长的长度
那么dp[i][j]=max{
if(a[i][j]>=a[i-1][j]) dp[i-1][j]+1
if(a[i][j]>=a[i][j-1]) dp[i][j-1]+1
}
最后答案是最大的dp[i][j]
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define FOR(i,n) for(i=0;i<(n);i++)
#define CLR(a) memset(a,0,sizeof(a))
#define CIN(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
int dp[][];
int a[][];
int n,m;
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF){
int ans=;
for(i=;i<n;i++){
for(j=;j<m;j++){
scanf("%d",&a[i][j]);
dp[i][j]=;
if(i!=&&a[i-][j]<=a[i][j]){
dp[i][j]=max(dp[i][j],dp[i-][j]+);
}
if(j!=&&a[i][j-]<=a[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j-]+);
}
ans=max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
}
return ;
}