[luogu1004] 격자 추출수(dp, 아세)

3233 단어 상태 아세dp
누군가가 그림의 왼쪽 상단의 A에서 출발하면 아래로 걸어갈 수도 있고 오른쪽으로 걸어서 오른쪽 하단의 B점에 도달할 수도 있다.지나가는 길에 그는 네모난 칸의 수를 가져갈 수 있다(가져간 칸은 숫자 0으로 바뀔 것이다).이 사람은 A점에서 B점까지 모두 두 번 걸었고, 이러한 경로 두 개를 찾아내어 얻은 숫자와 최대치를 얻었다.
INPUT 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0
OUTPUT 67 
#include
using namespace std;
const int maxn=101;

int a[maxn][maxn],f[maxn*2][maxn][maxn];
int n,m;

int main(){
    cin>>n;
    int x=1,y,w;
    while (1){
        cin>>x>>y>>w;
        a[x][y]=w;
        if (x==0&&y==0&&w==0) break;
    }
    for (int l=2;l<=2*n;l++) //  
        for (int x1=1;x1<=n;x1++)
            for (int x2=1;x2<=n;x2++){
                        int y1=l-x1; 
                        int y2=l-x2;
                        if (y1<=0) continue;
                        if (y2<=0) continue;    
                        int s=f[l][x1][x2];     
                        s=max(s,f[l-1][x1-1][x2-1]);
                        s=max(s,f[l-1][x1][x2-1]);
                        s=max(s,f[l-1][x1-1][x2]);
                        s=max(s,f[l-1][x1][x2]);
                        f[l][x1][x2]+=s;
                        if (x1==x2&&y1==y2) f[l][x1][x2]+=a[x1][y1];   //  
                        else f[l][x1][x2]+=a[x1][y1]+a[x2][y2];
            }
    cout<2*n][n][n];
}
UE4 HoloLens 구축 실패 시 처음 본 기사
시즈 클래스를 조사했습니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage