植物大战僵尸

但是，这次僵尸来进攻时，这些格子里放的不是植物，而是脑子。僵尸不敢独吞，而是想把脑子收集回去给他的K个朋友一起分享，为了不引发各种麻烦，因此他收集的脑子是K+1的倍数。
假设僵尸在地图的下方，而他的家在地图上方，另外，这只僵尸不喜欢走直线，喜欢走斜线，因此他每次只会往左上角走或者往右上角走，每走到一个格子会把这个格子的所有脑子都收集起来，问，怎么走收集的脑子个数最多？他可以在最下方任意选择一个格子作为起点。

输入格式

第一行输入一个数T，表示测试数据个数，对于每组测试数据，第一行输入三个数n,m,k，n和m表示这个地图的大小，(0<n,m<=100)，k表示他有k个朋友。(0<=k<=10)，之后有n行，每行m个数，表示每个格子的脑子个数，每个数都在0到9之间，包括0和9，注意，这些数之间没有空格。

输出

对于每组测试数据，输出一个数，表示最多能收集多少个脑，如果没有走法符合条件，输出一个数-1。

样例输入

3
3 3 0
123
456
789
3 3 1
123
456
789
2 2 10
98
75

样例输出

17
16

-1

哎，最直白的做法

//2196 kb 34 ms
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int dp[105][105][11];
int a[105][105];
int mod;

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n, m, f;
        scanf("%d%d%d", &n, &m, &f);
        mod = f+1;
        char str[105];
        for(int i=0; i<n; i++){
            scanf("%s", str);
            for(int j=0; j<m; j++)
                a[i][j] = str[j] - '0';
        }
        memset(dp, -1, sizeof(dp));
        for(int j=0; j<m; j++){
            int t = a[n-1][j] % mod;
            dp[n-1][j][t] = a[n-1][j];
        }
        for(int i=n-1; i>=1; i--){
            for(int j=0; j<m; j++){
                if(j-1 >= 0){
                    for(int k=0; k<mod; k++){
                        if(dp[i][j][k] >= 0){
                            int t = (dp[i][j][k] + a[i-1][j-1]) % mod;
                            dp[i-1][j-1][t] = max(dp[i-1][j-1][t], dp[i][j][k] + a[i-1][j-1]);
                        }
                    }
                }
                if(j+1 < m){
                    for(int k=0; k<mod; k++){
                        if(dp[i][j][k] >= 0){
                            int t = (dp[i][j][k] + a[i-1][j+1]) % mod;
                            dp[i-1][j+1][t] = max(dp[i-1][j+1][t], dp[i][j][k] + a[i-1][j+1]);
                        }
                    }
                }
            }
        }
        int res = -1;
        for(int j=0; j<m; j++){
            res = max(res, dp[0][j][0]);
        }
        if(res == -1) printf("-1\n");
        else printf("%d\n", res);
    }
    return 0;
}