hdu 6416 dp

Rikka with Seam Problem Description Seam carving is a novel algorithm for resizing images while maintaining as much information as possible from the source image.
Now, Rikka is going to use seam carving method to deal with an n×m black and white picture. We can abstract this picture into an n×m 01 matrix A.
A K-seam of this picture is an integer sequence a which satisfies the following conditions: 1. |a|=n, ai∈[1,m]. 2. |ai−ai+1|≤K, ∀i∈[1,n).
After choosing a K-seam a, Rikka reduces the size of the picture by deleting pixels (i,ai), and then she gets a matrix A′ of size n×(m−1).
For example, if the chosen seam is [1,2,3] and the picture is 100 111 000
the result matrix will be 00 11 00
Rikka finds that deleting different seams may get the same result. In the previous example, seam [1,2,3],[1,2,1],[1,2,2],[1,1,1] are equivalent.
Now Rikka wants to calculate the number of different matrixes she can get by deleting exactly one K-seam.
Input The first line contains a single integer t(1≤t≤103), the numebr of testcases.
For each testcase, the first line contains three numbers n,m,K(2≤n,m≤2×103,1≤K≤m).
Then n lines follow, each line contains a 01 string of length m which describes one row of the matrix.
The input guarantees that there are at most 5 testcases with max(n,m)>300.
Output For each testcase, output a single line with a single number, the answer modulo 998244353.
Sample Input 3 2 2 1 00 10 5 5 1 00100 10101 00100 01000 11101 5 5 2 00100 10101 00100 01000 11101
Sample Output 2 70 199 문제: n*m의 0, 1 행렬을 제시합니다. 한 줄마다 한 개의 수를 삭제할 수 있습니다. 두 줄마다 삭제한 숫자의 아래에 표시된 절대값의 차이는 k를 초과하지 않습니다. 모든 실행 가능한 방안에서 몇 개의 다른 행렬을 얻을 수 있는지 물어보십시오.방법: 먼저 각 줄을 분류한다. 만약에 이 줄에서 두 점을 삭제한 결과가 같다면 그들은 같은 종류라고 생각하고 서로 인접한 점이 수치가 같다면 그들은 같은 종류이다. 예를 들어 제목의 예이다.100 111 000은 122 111 111로 나눌 수 있다. 각 상태에 대해 첫 번째 줄의 유형, 두 번째 줄의 유형, 세 번째 줄의 유형으로 나눌 수 있다. 만약에 이 세 가지 유형이 같다면 그들이 얻은 결과가 똑같다고 생각할 수 있다. 그리고 dp를 만들 수 있다. 먼저 두 개의 dp수조를 열고 d[i][j], p[i][j]에 대해p[i][j]는 i행까지 대표할 때 마지막 선택은 j의 다른 방안 수이다. d[i][j]는 (i, j)이라는 점이 가지고 있는 것을 대표하지만 (i, j-1)이라는 점에 없는 상태수를 나타낸다. 그리고 갱신할 때 알 수 있는 점이 (i, j)에 도착하는 모든 상태는 바로 그 윗층(i-1, j-k)에서 (i-1, j+k)까지의 모든 다른 상태이다. 물론 이 안에는 중복된 상태가 많다. 그러면 생각이 있다.(i, j) 이 상태에 (i-1, j-k) 안의 모든 상태를 더하고 (i-1, j-k-1) 있는 상태를 더하면 (i-1, j-k) 없는 상태를 더하면 (i-1, j-k) 있는 상태인데 (i-1, j-k+2) 있는 상태인데 (i-1, j-k+1), (i-1, j-k) 없는 상태를 더하면 돼. 실현되면: 앞에 있는 d[i][j]를 기억해라. 한 점 있는 것은 있지만 앞에 있는 점 없는 상태를 보존하면 (i, j, j)그것의 방안수는 바로 p[i-1][j-k]+sum(d[i-1][j-k+1], d[i-1][j-k+2],,, dp[i-1][j+k])이다. 왜 그런지 두 점이 같은 상태를 가진 전제는 그들이 같은 줄의 같은 종류에 있다는 것이다.관찰을 통해 같은 줄에 대한 세 개의 점 x, y,z,x를 발견할 수 있다

#include
using namespace std;
const int N = 2005;
int d[N][N],p[N][N];
char st[N][N];
const int mod = 998244353;
void add(int &x,int y){
    /*x += y;
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;*/
    x += y;

    x %= mod;
    x += mod;
    x %= mod;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        /*memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));*/
        for(int i = 0;i <= n;i ++){
            for(int j = 0;j <= m;j ++) d[i][j] = p[i][j] = 0;
        }
        for(int i = 1;i <= n;i ++){
            scanf("%s",st[i]+1);
        }
        for(int i = 1;i <= m;i ++){
            if(st[1][i] != st[1][i-1]) d[1][i] = 1;
            p[1][i] = 1;
        }
        for(int i = 1;i <= n-1;i ++){
            for(int j= 1;j <= m;j ++){
                int nl= max(1,j-k);
                int nr = min(m+1,j+k);
                //cout <' ' <' '<' '<< nr <<' '<' '<
1][nl],d[i][j]);
                add(p[i+1][nr],-d[i][j]);
                if(j+k<=m){
                    add(p[i+1][nr],p[i][j]);
                    add(p[i+1][nr+1],-p[i][j]);
                }
            }
            for(int j = 1;j <= m;j ++){
                add(p[i+1][j],p[i+1][j-1]);
                if(st[i+1][j] != st[i+1][j-1]) d[i+1][j] = p[i+1][j];
                else if(j+k<= m) d[i+1][j] = d[i][j+k];
            }
        }
        /*for(int i = 1;i <= n;i ++){
            for(int j= 1;j <= m;j ++){
                    cout << i<< ' '<' '<< d[i][j] << ' ' << p[i][j] << endl;
            }
        }*/
        int ans=  0;
        for(int i= 1;i <= m;i ++) add(ans,d[n][i]);
        printf("%d
",ans);
    }

    return 0;
}