HDU 2571:운명(DP)

Problem I
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 48   Accepted Submission(s) : 25
Problem Description
유 곡 을 건 너 는 것 은 대마 왕 레 몬 과 무한 접근 했다 는 것 을 의미한다!그러나 yifenfei 가 일부 새우 병 게 장 을 참살 한 후에 다시 운명 의 미로 에 직면 하 게 될 것 이 라 고 누가 생각 할 수 있 겠 는가?이것 은 마왕 lemon 이 세운 또 다른 기관 이다.누구 든 미로 에 1 시간 이상 갇 히 면 죽는다 는 것 을 알 아야 한다!불쌍 한 이 펜 페 이 는 MM 을 구하 기 위해 정 의 롭 게 미궁 으로 뛰 어 들 었 다.집착 하 는 그 를 도와 주자!운명 의 큰 미 로 는 2 차원 의 격자 배열 로 볼 수 있 습 니 다.아래 그림 에서 보 듯 이[img]../../../data/images/C164-1005-1jpg[/img]yifenfei 는 처음에 왼쪽 상단 에 있 었 습 니 다.목적 은 당연히 오른쪽 아래 에 있 는 마왕 이 있 는 곳 에 도착 하 는 것 입 니 다.미궁의 모든 칸 은 행운 의 여신 의 미련 이나 고통 의 마왕 의 저 주 를 받 기 때문에 각 칸 은 하나의 값 에 대응 하여 그곳 에 가면 자동 으로 대응 하 는 값 을 얻 을 수 있 습 니 다.현재 yifenfei 는 오른쪽 이나 아래로 만 갈 수 있 고 다음 에는 한 칸 만 갈 수 있 도록 규정 되 어 있다.그러나 오른쪽으로 가면 매번 한 칸 을 걷 거나 이 줄 에 도착 할 수 있 는 열 수 는 현재 있 는 열의 배수 칸 입 니 다.즉,현재 칸 이(x,y)이면 다음 단 계 는(x+1,y),(x,y+1)또는(x,y*k)중 k>1 일 수 있 습 니 다.마왕 레 몬 을 최대한 파악 하기 위해 이 페 이 는 이 운명 의 미로 에서 가장 큰 행운 치 를 얻 고 싶 어 한다.[img]../../../data/images/C164-1005-2.jpg[/img]
 
Input
입력 데 이 터 는 먼저 정수 C 로 테스트 데이터 의 그룹 수 를 나타 낸다.각 조 의 테스트 데이터 의 첫 줄 은 두 개의 정수 n,m 로 각각 줄 수 와 열 수(1<=n<20,10<=m<=1000)를 나타 낸다.다음은 n 줄 데이터 입 니 다.줄 마다 m 개의 정 수 를 포함 하고 n 줄 m 열 에 해당 하 는 행운 치 K(|k|<100)를 표시 합 니 다.
 
Output
각 그룹의 테스트 데이터 에 대응 하여 하나의 정 수 를 출력 하여 yifenfei 가 얻 을 수 있 는 최대 행운 치 를 표시 하 십시오.
 
Sample Input

   
   
   
   

    
    
    
    1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10

   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    52
   
   
   
   

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=20+5;
const int MAXM=1000+5;
int f[MAXN][MAXM];
int MAX(int x,int y){	return x>y?x:y;}
int main()
{
	freopen("123.txt","r",stdin);
	int N,n,m,i,j,k;
	cin>>N;
	while(N--)
	{
		scanf("%d%d",&n,&m);

		for(i=0;i<=n;i++)
			for(j=0;j<=m;j++)
			{
				if(i&&j)scanf("%d",&f[i][j]);
				else f[i][j]=-1000000009;
			}


		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(i==1&&j==1)continue;//          
				int max=MAX(f[i-1][j],f[i][j-1]);
				if(j>1)max=MAX(max,f[i][1]);//        ，         
				
				for(k=2;k<=35;k++)
					if(j%k==0)
					{
						if(j/k==1)continue;
						max=MAX(max,MAX(f[i][k],f[i][j/k]));
					}
				f[i][j]+=max;
			}
		printf("%d
",f[n][m]);
	}
	return 0;
}