题意:= =中文题
思路一:比赛时队友想的。。。然后我赛后想了一下想了个2维dp,但是在转移的时候,貌似出了点小问题...吧?然后就按照队友的思路又写了一遍。
定义dp[i][j][k],表示第i列,放j个,剩下k个的种类数。其中j<=2, k<=2,j<=2的来源是只往上、下放。然后状态转移就是
dp[i][j][a[i] - j - k] = (dp[i][j][a[i] - j - k] + p[j] * dp[i - 1][k][j]) % mod;
//看看会不会爆int!数组会不会少了一维! //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") /* 定义dp[i][j][k]表示第i个人放了j个剩下k个的种类数 */ const LL mod = 100000007; const int maxn = 1e4 + 5; LL dp[maxn][3][6]; char ch[maxn]; int a[maxn]; int n; LL p[3] = {1, 2, 1}; LL solve(){ memset(dp, 0, sizeof(dp)); for (int i = 0; i <= 2; i++) { if (a[1] - i > 2) continue; if (a[1] - i < 0) break; dp[1][i][a[1] - i] = p[i]; } for (int i = 2; i <= n; i++){ for (int j = 0; j <= 2; j++){ for (int k = 0; k <= 2; k++){ if (a[i] - j - k > 2) continue; if (a[i] - j - k < 0) break;///目前放入j个,dp[i-1]剩下j个 dp[i][j][a[i] - j - k] = (dp[i][j][a[i] - j - k] + p[j] * dp[i - 1][k][j]) % mod; } } } LL ans = 0; for (int i = 0; i <= 2; i++){ if (i > a[n]) break; ans = (ans + dp[n][i][0]) % mod; } return ans; } int main(){ int t; scanf("%d", &t); while (t--){ scanf("%s", ch); n = strlen(ch); bool flag = true; for (int i = 0; ch[i] != '