여름방학 캠프 4주차 수요경기 A-운명동태 기획

A - 운명
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status 
Practice 
HDU 2571
Description
유곡을 건너는 것은 대마왕 레몬과 무한히 가까워졌다는 것을 의미한다! 
그런데 이펜피이가 새우병과 게장들을 참살한 후에 다시 운명의 미로에 직면하게 될 줄은 누가 알았겠는가. 이것은 마왕 레몬이 세운 또 다른 기관이다.누구든지 1시간 이상 미궁에 갇히면 죽는다는 것을 알아야 한다! 
불쌍한 이펜피이는 MM을 구하러 가기 위해 의리 있게 미궁으로 뛰어들었다.우리 함께 집착하는 그를 도와줍시다! 
운명의 큰 미로는 2차원 격자 진열로 볼 수 있다. 아래 그림과 같다.
이 infei는 처음에 왼쪽 상단에 있었는데, 목적은 당연히 오른쪽 하단에 있는 대마왕의 소재지에 도착하는 것이다.미로의 모든 칸은 행운의 여신이 그리워하거나 고통스러운 마왕의 저주를 받기 때문에 모든 칸은 하나의 값에 대응하고 그곳에 가면 자동으로 대응하는 값을 얻는다. 
현재 이펜피는 오른쪽이나 아래로, 아래로는 한 칸만 갈 수 있도록 규정되어 있다.그러나 오른쪽으로 가면 매번 한 칸씩 가거나 이 줄에 도착할 수 있는 열수는 현재 있는 열의 배수 배수의 칸이다. 즉, 현재 칸이 (x, y)이면 다음 칸은 (x+1, y), (x, y+1) 또는 (x, y*k) 중 k>1이다. 
마왕 레몬을 최대한 처치하기 위해 이펜피는 이 운명의 미로에서 가장 큰 행운치를 얻기를 바란다. 
 
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 
      
      
      
      

분석:
이것은 동적 기획 문제이자 유명한 01배낭으로 한 걸음 한 걸음 가장 좋은 결과를 얻을 수 있다. 계속 추진하면 마지막까지 가장 좋은 결과가 될 것이다.
그 외에 문제의 사고방식에 따라 가면 몇 가지 상황이 있으면 판단하면 된다
또 하나의 전문적인 상태 이동 방정식이 있다

 for(j=1;j<=m;j++)
            f[i][j]=ma(i,j)+a[i][j];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<stdio.h>
#include<string.h>
int a[25][1010],f[25][1010];
int ma(int i,int j)
{
    int s=-11000000;
if(f[i-1][j]>s)
   s=f[i-1][j];
    if(f[i][j-1]>s)
    s=f[i][j-1];
for(int k=2;k<=j;k++)
    if(j%k==0&&f[i][j/k]>s)
    s=f[i][j/k];
return s;
}
int main()
{
    int c,n,m,i,j,s;
    scanf("%d",&c);
    while(c--)
    {
        memset(f,-9999999,sizeof(f));
        f[0][1]=f[1][0]=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            f[i][j]=ma(i,j)+a[i][j];
            printf("%d
",f[n][m]);
    }
    return 0;
}