本文共 1854 字，大约阅读时间需要 6 分钟。
题目：
思路：
这是刚练dp后做比赛遇到的第一道dp题
比赛时想了一个状态转移方程，f[i][j][k][l][2], i和j表示在第i行j列， k和l表示人和剑的能量，最后一维0表示当前这个能量给人补充，1表示给剑补充 转移为： f[i][j][k][l][0] = f[i-1][j][k-mat[i][j]][l][1]+f[i][j-1][k-mat[i][j]][l][1]; f[i][j][k][l][1] = f[i-1][j][k][l-mat[i][j]][0]+f[i][j-1][k][l-mat[i][j]][0]; 但是在实现时，还是遇到了各种问题，总是得不到样例,这样一直到比赛结束... 结束后继续调试，终于调试出来了，结果一交，477*477*11*11的复杂度还是TLE了... 然后就很自然地想到了降维，把人和剑的能量变成了人和剑的能量差值 但是降维后，状态转移就变得不清楚了 比如差值为2的时候，有[0,2],[1,3],[2,4]...[8,10], 在不同范围区间内进行加减运算，会得到不一样的结果， 比如[0,2]，0-2=9，变成[9,2]差值为7 而[2,4], 2-2=0, 变成[0,2]差值为-2 就不知道该怎样状态转移了。 后来，换了一种思考方式，对于差值k，对应人和剑的能量[x,y], 表示x加上k会等于y，就可以想通了 而状态转移[x-mat[i][j], y]和[x, y-mat[i][j]]怎样变成对应状态的差值呢？ 显然，前者让差值增大了mat[i][j], 因为y-x-(y-(x-mat[i][j])) = mat[i][j],而后者让差值减少了mat[i][j] 总之，AC了这道题还是让我非常开心的 ^_^代码：
#include#include #include #include #define MP make_pair#define SQ(x) ((x)*(x))typedef long long int64;const double PI = acos(-1.0);const int MAXN = 110;const int INF = 0x3f3f3f3f;using namespace std;const int MOD = 1000000007;int n, m;int f[2][480][22][2];int mat[480][480];char str[1000];int main(){ int nCase, cas=1; scanf("%d", &nCase); while(nCase--){ scanf("%d%d%*c", &n, &m); for(int i=1; i<=n; ++i){ gets(str); for(int j=1; j<=m; ++j) mat[i][j] = str[j-1]-'0'; } memset(f, 0, sizeof(f)); int ans = 0; bool p = 0; for(int i=1; i<=n; ++i){ p = !p; memset(f[p], 0, sizeof(f[p])); for(int j=1; j<=m; ++j){ for(int k=0; k<=10; ++k){ int x1 = (k+mat[i][j])%11; int x2 = (k-mat[i][j]+11)%11; f[p][j][k][0] += ((f[!p][j][x1][1]+f[p][j-1][x1][1])%MOD)%MOD; f[p][j][k][1] += ((f[!p][j][x2][0]+f[p][j-1][x2][0])%MOD)%MOD; } // 增加一种从当前点开始出发的情况 ++f[p][j][11-mat[i][j]][0]; } for(int j=1; j<=m; ++j){ ans += (f[p][j][0][0] + f[p][j][0][1])%MOD; ans %= MOD; } } printf("Case %d: %d\n",cas++, ans); } return 0;}
转载地址：http://zvzni.baihongyu.com/