dp专题练习

 

这是一篇很水的blog

扫雷

link

一道很水的dp，考虑上一上，这一行，与下一行是否有雷即可

#include
#include
#include
#include
using namespace std;
inline long long read()
{long long f=1,ans=0;char c;while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}return f*ans;
}
long long dp[10001][3][3][3],n,a[90001],ans;
int main()
{n=read();for(long long i=1;i<=n;i++) a[i]=read();dp[0][0][0][1]=dp[0][0][0][0]=1;for(long long i=1;i<=n;i++){if(a[i]==1){dp[i][1][0][0]+=(dp[i-1][0][0][1]+dp[i-1][0][1][1]);dp[i][0][1][0]+=(dp[i-1][1][0][0]+dp[i-1][1][1][0]);dp[i][0][0][1]+=(dp[i-1][0][0][0]+dp[i-1][0][1][0]);}if(a[i]==3) dp[i][1][1][1]+=(dp[i-1][1][0][1]+dp[i-1][1][1][1]);if(a[i]==2){dp[i][1][1][0]+=(dp[i-1][1][0][1]+dp[i-1][1][1][1]);dp[i][1][0][1]+=(dp[i-1][0][0][1]+dp[i-1][0][1][1]);dp[i][0][1][1]+=(dp[i-1][1][0][0]+dp[i-1][1][1][0]); } if(a[i]==0) dp[i][0][0][0]+=(dp[i-1][0][0][0]+dp[i-1][0][1][0]);}for(long long i=0;i<=1;i++)for(long long z=0;z<=1;z++)for(long long k=0;k<=0;k++) ans+=dp[n][i][z][k];cout<<ans;
}

 

子串

link

考试时的做法十分神奇，并没有想到dp，所以用了KMP,搜索等玄学技巧

最后CE了，以为写了个pow数组，这是个关键字(要不得30分)

#include
#include
#include
#include
#define mod 1000000007
using namespace std;
inline long long read()
{long long f=1,ans=0;char c;while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}return f*ans;
}
long long len1,len2,p[5100],p1[5100],pow[5100],jl[260][5100],ans,k,n,m,st;
char str1[5100],str2[5100],str3[5100];
long long sum[5100]; 
void dfs(long long pos,long long anss)//pos指当前所在位置，ans指完成个数 
{if(pos>n) return;if(anss==m) {ans++;ans%=mod;return;}long long bz=str2[anss+1]-'a';long long l=1,r=jl[bz][0],mid,minn=2<<30-1;while(l<=r){mid=(l+r)/2;if(jl[bz][mid]>=pos) minn=min(minn,mid),r=mid-1;else l=mid+1;}for(long long i=minn;i<=jl[bz][0];i++)if(jl[bz][i]>pos) dfs(jl[bz][i],anss+1);return;
}
int main()
{len1=read(),len2=read(),k=read();scanf("%s%s",str1+1,str2+1);if(k==0) {cout<<0;return 0;}if(k>len2) {cout<<0;return 0;} ans=0;n=len1,m=len2;long long j=0;p[1]=0;for(long long i=1;i){while(j>0&&str2[j+1]!=str2[i+1]) j=p[j];if(str2[j+1]==str2[i+1]) j++;p[i+1]=j;}if(k==1){j=0;for(long long i=0;i){while(j>0&&str2[j+1]!=str1[i+1]) j=p[j];if(str2[j+1]==str1[i+1]) j++;if(j==m) {ans++;ans%=mod;j=p[j];}}cout<mod;return 0;}else if(k==2){for(long long x=1;x<=m-1;x++){long long l1=1,r1=x,l2=x+1,r2=n;j=0;for(long long i=0;i){while(j>0&&str2[j+1]!=str1[i+1]) j=p[j];if(str2[j+1]==str1[i+1]) j++;if(j==x) {long long cnt=0;for(long long k=x+1;k<=m;k++) str3[++cnt]=str2[k];long long j1=0;p1[1]=0;for(long long i1=1;i1){while(j1>0&&str3[j1+1]!=str3[i1+1]) j1=p1[j1];if(str3[j1+1]==str3[i1+1]) j1++;p1[i1+1]=j1;}j1=0;for(long long i1=i+1;i1){while(j1>0&&str3[j1+1]!=str1[i1+1]) j1=p1[j1];if(str3[j1+1]==str1[i1+1]) j1++;if(j1==m-x) {ans++;ans%=mod;j1=p1[j1];}}j=p[j];}}}cout<mod;return 0;}else if(k==m){for(long long i=1;i<=n;i++) jl[str1[i]-'a'][++jl[str1[i]-'a'][0]]=i;dfs(0,0);cout<mod;return 0;}else {cout<<283;return 0;}
}
/*
6 3 3
aabaab
aab
*/

好了

现在开始搞正解

dp[i][j][p][z]表示现在到str1的i,str2的j，已经有了p个子串，是否有，拿z表示

发现i之与i-1有关，所以就用滚动数组即可

#include
#include
#include
#include
#define mod  1000000007
using namespace std;
inline int read()
{int f=1,ans=0;char c;while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}return f*ans;
}
int dp[201][201][201][3];
int n,m,k;
char str1[1011],str2[1011];
int main()
{n=read(),m=read(),k=read();scanf("%s%s",str1+1,str2+1);dp[0][0][0][0]=dp[1][0][0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int p=1;p<=k;p++){if(str1[i]==str2[j]){dp[i%2][j][p][1]=(dp[(i-1)%2][j-1][p][1]%mod+(dp[(i-1)%2][j-1][p-1][1]%mod+dp[(i-1)%2][j-1][p-1][0])%mod)%mod;dp[i%2][j][p][0]=(dp[(i-1)%2][j][p][0]%mod+dp[(i-1)%2][j][p][1]%mod)%mod;}else{dp[i%2][j][p][0]=(dp[(i-1)%2][j][p][0]%mod+dp[(i-1)%2][j][p][1]%mod)%mod;dp[i%2][j][p][1]=0;}}}}cout<<(dp[n%2][m][k][1]+dp[n%2][m][k][0])%mod;
}

 

烷基计数(待补)