2016 - 植物大战僵尸
都玩过植物大战僵尸吧
但是，这次僵尸来进攻时，这些格子里放的不是植物，而是脑子。僵尸不敢独吞，而是想把脑子收集回去给他的K个朋友一起分享，为了不引发各种麻烦，因此他收集的脑子是K+1的倍数。<br />
假设僵尸在地图的下方，而他的家在地图上方，另外，这只僵尸不喜欢走直线，喜欢走斜线，因此他每次只会往左上角走或者往右上角走，每走到一个格子会把这个格子的所有脑子都收集起来，问，怎么走收集的脑子个数最多？他可以在最下方任意选择一个格子作为起点。
题目输入
第一行输入一个数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
C++解答
/* *===================== *File Name:a.cpp *Author: qqspeed *Date: 2014年 07月 17日 星期四 11:18:22 CST *===================== */ #include <stdio.h> #include <string.h> #include <iostream> #include <string> #include <queue> #include <stack> #include <map> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,s,t) for(int i=s;i<t;i++) #define red(i,s,t) for(int i=s-1;i>=t;i--) #define ree(i,now) for(int i=head[now];i!=-1;i=edge[i].next) #define clr(a,v) memset(a,v,sizeof a) #define L t<<1 #define R t<<1|1 #define MID int mid=(l+r)>>1 #define max(a,b) (a<b?b:a) #define min(a,b) (a<b?a:b) #define SQR(a) ((a)*(a)) inline int input(){ int ret=0;bool isN=0;char c=getchar(); while(c<'0' || c>'9'){ if(c=='-') isN=1; c=getchar(); } while(c>='0' && c<='9'){ ret=ret*10+c-'0'; c=getchar(); } return isN?-ret:ret; } inline void output(int x){ if(x<0){ putchar('-');x=-x; } int len=0,data[11]; while(x){ data[len++]=x%10;x/=10; } if(!len) data[len++]=0; while(len--) putchar(data[len]+48); putchar('\n'); } int t,n,m,k; char s[110][110]; int a[110][110]; int dp[110][110][15]; bool in(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m; } int main(){ //freopen("1","w",stdout); t=input(); while(t--){ n=input(),m=input(),k=input(); k++; rep(i,0,n) scanf("%s",s[i]); rep(i,1,n+1) rep(j,1,m+1){ a[i][j]=s[i-1][j-1]-'0'; } clr(dp,-1); rep(i,1,m+1){ dp[n][i][a[n][i]%k]=a[n][i]; } red(i,n,1){ rep(j,1,m+1){ rep(r,0,k){ int x=i+1,y=j-1; if(in(x,y) && dp[x][y][r]!=-1){ int nxt=(r+a[i][j])%k; int val=dp[x][y][r]+a[i][j]; if(dp[i][j][nxt]==-1 || dp[i][j][nxt]<val){ dp[i][j][nxt]=val; } } y=j+1; if(in(x,y) && dp[x][y][r]!=-1){ int nxt=(r+a[i][j])%k; int val=dp[x][y][r]+a[i][j]; if(dp[i][j][nxt]==-1 || dp[i][j][nxt]<val){ dp[i][j][nxt]=val; } } } } } vector<char>v; int id,Max=-1; rep(i,1,m+1){ if(dp[1][i][0]!=-1){ if(Max<dp[1][i][0]){ id=i;Max=dp[1][i][0]; } } } if(Max==-1){ puts("-1"); } else{ printf("%d\n",Max); /* rep(i,2,n+1){ int x=id+1; if(in(i,x)){ int r=(Max-a[i-1][id])%k; if(dp[i][x][r]==Max-a[i-1][id]){ v.push_back('L'); Max-=a[i-1][id]; id=x; continue; } } x=id-1; if(in(i,x)){ int r=(Max-a[i-1][id])%k; if(dp[i][x][r]==Max-a[i-1][id]){ v.push_back('R'); Max-=a[i-1][id]; id=x; continue; } } } printf("%d\n",id); int S=v.size(); red(i,S,0){ printf("%c",v[i]); } puts("");*/ } } return 0; }