【dp】 poj 1157

3499 단어 poj
괜찮은 dp 입문 문제에서 dp 행렬을 그려낸다. 각 dp[i][j]는'그 위'의 상태나'그 왼쪽 위'의 상태로 전환된다. 그러면 우리는 대각선과 위쪽을 골라 삼각 dp추론을 한다.
 
#include<stdio.h>

#include <iostream>

using namespace std;

#define MAX 110

int value[MAX][MAX];

int f[MAX][MAX];

int F,V;

int main()

{

// freopen("in.txt","r",stdin);

 int i,j;

 scanf("%d%d",&F,&V);

 for(i=0;i<F;i++){

  for(j=0;j<V;j++){

   scanf("%d",&value[i][j]);

  }

 }

 f[0][0]=value[0][0];

 for(i=1;i<V;i++)

        f[0][i]=max(f[0][i-1],value[0][i]);//  1      

 for(i=1;i<F;i++)

  f[i][i]=f[i-1][i-1]+value[i][i];  // i    i      ,  i   i   ,           

 for(i=1;i<F;i++){

  for(j=i+1;j<V;j++){

    f[i][j]=max(f[i-1][j-1]+value[i][j],f[i][j-1]);

  }

 }

 printf("%d
",f[F-1][V-1]); return 0; }

좋은 웹페이지 즐겨찾기