2016年3月

忙里偷闲终于做出了这道题。
自己推dp推不出听大神讲听不懂就只能自己对着别人的题解脑补了。
好在脑补出来了……
总之感觉真的好巧妙的东西,就长这样。

$$ f(i,j,k) = \\begin{cases} \\sum_{i'<i} f(i',j-1,k-1), \& \\text{if S[i]==T[j] && S[i-1]!=T[j-1]} \\\\ [\\sum_{i'<i} f(i',j-1,k-1)]+f(i-1,j-1,k) \& \\text{if S[i]==T[j] && S[i-1]==T[j-1]} \\\\ \\end{cases} $$

莫名其妙地一直只有10pts,然后把k这一维提前后就A了……真是莫名其妙……难道是数组清零问题?
莫名其妙……

UPD: 真是数组清零问题……但究竟为何还待深究,不过
千万记住滚动数组滚动时要全部清零!!!

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int mod = 1000000007, maxn = 1000 + 10, maxm = 200 + 10;
long long dp[2][maxn][maxm] = {0}, sigma[2][maxn][maxm] = {0};
int n, m, kt;
int main()
{
    read(n, m, kt);
    static char a[maxn], b[maxn];
    scanf("%s%s", a + 1, b + 1);
    dp[0][0][0] = sigma[0][0][0] = 1;
    for(int i = 0; i <= n; i++)
        sigma[0][i][0] = 1;
    for(int k = 1; k <= kt; k++)
    {
        memset(dp[k&1], 0, sizeof dp[k&1]);
        memset(sigma[k&1],0,sizeof sigma[k&1]);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                dp[k&1][i][j] = sigma[k&1][i][j] = 0;
                if(a[i] == b[j])
                {
                    dp[k & 1][i][j] = sigma[~k & 1][i - 1][j - 1];
                    if(a[i - 1] == b[j - 1])
                        dp[k & 1][i][j] = (dp[k & 1][i][j] + dp[k & 1][i - 1][j - 1]) % mod;
                }
                sigma[k&1][i][j] = (sigma[k&1][i-1][j] + dp[k&1][i][j]) % mod;
            }
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        ans = (ans + dp[kt & 1][i][m]) % mod;
    printf("%d\n", ans);
    return 0;
}