로곡-P1004 - 체크수 - 간단dp

4508 단어
https://www.luogu.org/problemnew/show/P1004
이 문제는 간단한 dp로 분류되었지만 조금도 간단하지 않은 것 같다...이런 두 번 하는 dp는 정말 어떻게 쓰는지 잘 모르겠다.만약 욕심을 두 번 낸다면 이것이 최우선이라는 것을 증명할 수 없을 것 같다.
문제풀이를 직접 보면 문제풀이는 4개의 차원을 설정하고 두 사람이 동시에 가야 하는데...그런데 어떻게 같은 물건을 두 사람이 가지는 것을 피할 수 있습니까?
dp[i][j][k][l]를 설정하면 첫 번째 사람이ij에 도착하고 두 번째 사람이kl에 도착하면 실현할 수 있는 가장 큰 방법을 나타낸다. 그리고 1차원[p]을 더하면 현재 00,01,02,10,11,12,20,21,22개의 물품을 찾았고 dp의 내용은 바이커다!이렇게 하면 모든 메시지를 완벽하게 표현할 수 있다!이렇게 하면 같은 아이템은 한 상태를 다른 상태로 옮길 수 있습니다. 이 아이템이 동시에 획득되지 않도록 보증합니다!공간 복잡도?나는 왜 공간의 복잡도를 관리해야 합니까?이 dp 시간 복잡도는 모두 공간 복잡도와 동급이다.
 
자, 다른 사람의 상태 설정을 보고 아이디어를 찾아서 먼저 직접 써 보세요.
귀신이라고 써. 내가 갈게. 문제를 잘못 읽었어. 물건 두 개만 가져올 수 있는 게 아니라... 나 또 자야 돼...
 
두 사람이 동시에 걷는 것을 주의해라!만약 두 사람이 동시에 가지 않았다면 어떻게 되었을까?그러면 복잡도가 올라갈 뿐만 아니라 n.²,그리고 현재 칸이 다른 사람의 길에 빼앗겼는지 판단할 수 없다.
#include
using namespace std;
#define ll long long

int dp[10][10][10][10];
int a[10][10];

int main(){
    int n;
    scanf("%d",&n);
    int x,y,v;
    while(1){
        scanf("%d%d%d",&x,&y,&v);
        if(x==0&&y==0&&v==0)
            break;
        a[x][y]=v;
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int l=1;l<=n;l++){
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]));
                    dp[i][j][k][l]+=a[i][j];
                    if(i==k&&j==l)
                        ;
                    else
                        dp[i][j][k][l]+=a[k][l];
                }
            }
        }
    }
    printf("%d
",dp[n][n][n][n]);
}

 
다른 사람의 문제 해설 뒤에 쪽지와 회문을 전하는 경로도 있는데 이런 양쪽을 함께 하는 dp이다.
전재 대상:https://www.cnblogs.com/Yinku/p/10325524.html
Javascript에서 "This"의 고급 사용법을 드디어 알게 되었습니다.
Swift에서 ViewController 사용

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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