cf1800-2200的dp
codeforces1132f
题意：应该是懂得，然后题解在代码里面，比较意识流，看看就好了
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
1 /* 2 这种题给n=500就一种很浓浓的区间dp风格啊。。。。。。。。。。。。 3 首先我们 设 dp[l][r]为把l和r这个段的全部点都消去所用的最小操作 4 给一个样例 babaca 5 首先如果我们可以知道ai[l]==ai[r]的话我们可以通过合并的时候减少一次操作 6 然后这居然就可以了。。。。。。。。。。。？？？？？？？？？ 7 倒是真的无法反驳啊 8 首先肯定是要枚举断点的，枚举断点和-1 9 10 那就有一个问题，枚举断点后我们会存在一个情况，假如断点两端相等怎么办，你枚举到下一层 11 不就可以了吗？ 12 13 */ 14 #include <algorithm> 15 #include <iostream> 16 #include <cstdio> 17 #include <cstring> 18 #include <cmath> 19 #include <bitset> 20 typedef long long ll; 21 using namespace std; 22 char sz[510]; 23 int dp[510][510]; 24 int len; 25 int main(){ 26 scanf("%d",&len); 27 scanf("%s",sz+1); 28 for(int i=1;i<=len;i++) dp[i][i]=1;//这个要记得 29 for(int i=len;i>=1;i--){ 30 for(int j=i+1;j<=len;j++){ 31 dp[i][j]=(j-i+1);//这个初始化是最好的 32 //我们以段长初始化就保证不会犯错误 33 for(int k=i+1;k<=j;k++){ 34 if(sz[i]==sz[j]) dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j]-1); 35 else dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][j]); 36 } 37 } 38 } 39 cout<<dp[1][len]<<endl; 40 return 0; 41 }View Code
codeforces1117d
给出一个错误代码，原因应该很显然
1 /* 2 这题的状态转移方程还是挺好推的 3 但是我们不止这样就结束了啊。。。。。。。。。。 4 首先我们得到的状态转移方程是dp[i] = dp[i-1] + dp[i-m]; 5 dp[0]=0 1 到 m-1 dp[i]=1; 6 dp[m] =2; 7 如果继续变大的吧 dp[i] =dp[i-1] + dp[i-m]; 8 从 i==m+1算起 9 要算 n-m次 10 构造的矩阵： 11 [1 1] * [dp[i-1]] = [dp[i]] 12 [1 0] [dp[i-m]] [dp[i-1]] 13 然后我们就可以得到要算n-m次 14 然后就乱搞了啊 15 */ 16 #include <algorithm> 17 #include <iostream> 18 #include <cstdio> 19 #include <cstring> 20 #include <cmath> 21 #include <bitset> 22 typedef long long ll; 23 using namespace std; 24 const ll mod=1000000007; 25 ll n,m; 26 ll f[3][3]; 27 ll ans[3]; 28 ll tmp1[3]; 29 ll tmp2[3][3]; 30 31 void init(){ 32 f[1][1]=1;f[1][2]=1; 33 f[2][1]=1;f[2][2]=0; 34 ans[1]=2;ans[2]=1; 35 } 36 37 void query(){ 38 memset(tmp1,0,sizeof(tmp1)); 39 for(int i=1;i<=2;i++){ 40 for(int k=1;k<=2;k++){ 41 tmp1[i]=(tmp1[i]+(f[i][k]*ans[k])%mod)%mod; 42 } 43 } 44 for(int i=1;i<=2;i++) ans[i]=tmp1[i]; 45 } 46 47 void mul(){ 48 memset(tmp2,0,sizeof(tmp2)); 49 for(int i=1;i<=2;i++){ 50 for(int j=1;j<=2;j++){ 51 for(int k=1;k<=2;k++){ 52 tmp2[i][j]=(tmp2[i][j]+(f[i][k]*f[k][j])%mod)%mod; 53 } 54 } 55 } 56 for(int i=1;i<=2;i++) 57 for(int j=1;j<=2;j++) 58 f[i][j]=tmp2[i][j]; 59 } 60 61 void fast_pow(ll t){ 62 while(t){ 63 if(t%2==1) query(); 64 mul(); 65 t/=2; 66 } 67 } 68 69 int main(){ 70 scanf("%lld%lld",&n,&m); 71 if(n<=m-1){ 72 printf("1\n"); 73 }else if(n==m){ 74 printf("2\n"); 75 }else{ 76 init(); 77 fast_pow(n-m); 78 printf("%lld\n",ans[1]%mod); 79 } 80 return 0; 81 }View Code
上面这个代码为什么是错误的呢
原因如下：我在变化过程中这种只能面对m==2的情况，变化几次后我的f【i-m】的值早就已经不对了。。。。。。。。。。
接下来是正确代码：
1 /* 2 这题的状态转移方程还是挺好推的 3 但是我们不止这样就结束了啊。。。。。。。。。。 4 首先我们得到的状态转移方程是dp[i] = dp[i-1] + dp[i-m]; 5 dp[0]=0 1 到 m-1 dp[i]=1; 6 dp[m] =2; 7 如果继续变大的吧 dp[i] =dp[i-1] + dp[i-m] 8 然后我们就可以得到要算n-m次 9 然后就乱搞了啊 10 */ 11 #include <algorithm> 12 #include <iostream> 13 #include <cstdio> 14 #include <cstring> 15 #include <cmath> 16 #include <bitset> 17 typedef long long ll; 18 using namespace std; 19 const ll mod=1000000007; 20 ll n,m; 21 ll f[110][110]; 22 ll ans[110]; 23 ll tmp1[110]; 24 ll tmp2[110][110]; 25 26 void init(){ 27 memset(f,0,sizeof(f)); 28 f[1][1]=1;f[1][m]=1; 29 for(int i=2;i<=m;i++) f[i][i-1]=1; 30 ans[1]=2; 31 for(int i=2;i<=m;i++) ans[i]=1; 32 } 33 34 void query(){ 35 memset(tmp1,0,sizeof(tmp1)); 36 for(int i=1;i<=m;i++){ 37 for(int k=1;k<=m;k++){ 38 tmp1[i]=(tmp1[i]+(ans[k]*f[i][k])%mod)%mod; 39 } 40 } 41 for(int i=1;i<=m;i++) ans[i]=tmp1[i]; 42 } 43 44 void mul(){ 45 memset(tmp2,0,sizeof(tmp2)); 46 for(int i=1;i<=m;i++){ 47 for(int j=1;j<=m;j++){ 48 for(int k=1;k<=m;k++){ 49 tmp2[i][j]=(tmp2[i][j]+(f[i][k]*f[k][j])%mod)%mod; 50 } 51 } 52 } 53 for(int i=1;i<=m;i++) 54 for(int j=1;j<=m;j++) 55 f[i][j]=tmp2[i][j]; 56 } 57 58 void fast_pow(ll t){ 59 while(t){ 60 if(t%2==1) query(); 61 mul(); 62 t/=2; 63 } 64 } 65 66 int main(){ 67 scanf("%lld%lld",&n,&m); 68 if(n<=m-1){ 69 printf("1\n"); 70 }else if(n==m){ 71 printf("2\n"); 72 }else{ 73 init(); 74 fast_pow(n-m); 75 printf("%lld\n",ans[1]%mod); 76 } 77 return 0; 78 }View Code
更多精彩
