游客 注册 | 登录
中文 | En

2016 - 植物大战僵尸

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

都玩过植物大战僵尸吧 

但是，这次僵尸来进攻时，这些格子里放的不是植物，而是脑子。僵尸不敢独吞，而是想把脑子收集回去给他的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;
}
请先登陆