code forces 1051 d

看的这个题解：http://www.cnblogs.com/tobyw/p/9685639.html

写的比较清楚。

矩阵类型的计数题

比赛时感觉就像是个dp，然后就跳过了。

现在看着题解写一下，感觉还算可以理解。但是没有dp的思维啊，肯定想不出来的。。

 #include <bits/stdc++.h>

 using namespace std;

 long long dp[][][];

 const long long mod = ;

 int main() {

     long long n,k;

     cin>>n>>k;

     memset(dp,,sizeof(dp));

     dp[][][] = ; //

     dp[][][] = ; //

     dp[][][] = ; //

     dp[][][] = ; //11

     //cout<<k<<endl;

     for(int i = ; i <= n; i++) {

         // i列最多i * 2 个联通块

         for(int j = ; j <= (i << ); j++) {

             //cout<<dp[n][k][0]<<' '<<dp[n][k][1]<<' '<<dp[n][k][2]<<' '<<dp[n][k][3]<<endl;

             //cout<<j<<endl;

             // 这一列填00的

             dp[i][j][] = dp[i - ][j][] + dp[i - ][j][] + dp[i - ][j][] + dp[i - ][j - ][];

             dp[i][j][] %= mod;

             // 填01

             dp[i][j][] = dp[i - ][j - ][] + dp[i - ][j][] + dp[i - ][j - ][] + dp[i - ][j - ][];

             dp[i][j][] %= mod;

             // 填10

             dp[i][j][] = dp[i - ][j - ][] + dp[i - ][j - ][] + dp[i - ][j][] + dp[i - ][j - ][];

             dp[i][j][] %= mod;

             // 填11

             dp[i][j][] = dp[i - ][j - ][] + dp[i - ][j][] + dp[i - ][j][] + dp[i - ][j][];

             dp[i][j][] %= mod;

         }

     }

      long long ans = ;

      //cout<<dp[n][k][0]<<' '<<dp[n][k][1]<<' '<<dp[n][k][2]<<' '<<dp[n][k][3]<<endl;

      ans = ans + dp[n][k][] + dp[n][k][] + dp[n][k][] + dp[n][k][];

      ans = ans % mod;

      //cout<<ans<<endl;

      printf("%I64d\n", ans);

     return ;

 }

巴特西

code forces 1051 d

最新文章

热门文章