首页 > 代码库 > [luoguP1879] [USACO06NOV]玉米田Corn Fields（DP）

[luoguP1879] [USACO06NOV]玉米田Corn Fields（DP）

2024-09-28 04:50:39   211人阅读

传送门

 

说要统计方案，感觉就是个 Σ

而矩阵中只有 01 ，可以用二进制表示

这样，预处理出每一个每一行所有可能的状态 s

然后初始化第一行所有状态的方案数为 1

f[i][j] = Σf[i - 1][k] (k 和 j 不冲突，j 为第 i 行所有方案，k 为第 i - 1 行所有方案)

 

——代码

技术分享
 1 #include <cstdio> 2 #include <iostream> 3 #define mod 100000000 4  5 int n, m, ans; 6 int f[13][1 << 13], pos[13][1 << 13], s[13][1 << 13]; 7  8 inline int read() 9 {10     int x = 0, f = 1;11     char ch = getchar();12     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14     return x * f;15 }16 17 inline void dfs(int k, int i, int num)18 {19     if(i > pos[k][0])20     {21         s[k][++s[k][0]] = num;22         return;23     }24     dfs(k, i + 1, num);25     if((pos[k][i] ^ (pos[k][i - 1] + 1)) || (i == 1))26         dfs(k, i + 1, num + (1 << pos[k][i] - 1));27     else if((i ^ 1) && (pos[k][i] == pos[k][i - 1] + 1))28         if(((num >> pos[k][i - 1] - 1) & 1) ^ 1)29             dfs(k, i + 1, num + (1 << pos[k][i] - 1));30 }31 32 int main()33 {34     int i, j, k, x;35     n = read();36     m = read();37     for(i = 1; i <= n; i++)38         for(j = 1; j <= m; j++)39         {40             x = read();41             if(x) pos[i][++pos[i][0]] = j;42         }43     for(i = 1; i <= n; i++) dfs(i, 1, 0);44     for(i = 1; i <= s[1][0]; i++) f[1][i] = 1;45     for(i = 2; i <= n; i++)46         for(j = 1; j <= s[i][0]; j++)47             for(k = 1; k <= s[i - 1][0]; k++)48                 if(!(s[i][j] & s[i - 1][k]))49                 {50                     f[i][j] += f[i - 1][k];51                     if(f[i][j] >= mod) f[i][j] -= mod;52                 }53     for(i = 1; i <= s[n][0]; i++)54     {55         ans += f[n][i];56         if(ans >= mod) ans -= mod;57     }58     printf("%d\n", ans);59     return 0;60 }
View Code

 

[luoguP1879] [USACO06NOV]玉米田Corn Fields（DP）


联系
我们