체크수 (dp)

15416 단어 dp
제목은 N*N의 격자 그래프(N<=8)가 설치되어 있으며, 우리는 그 중 일부 칸에 정수를 채우고, 다른 칸에는 숫자 0을 넣는다.누군가가 그림의 왼쪽 상단의 A점에서 출발하면 아래로 걸어갈 수도 있고 오른쪽으로 걸어서 오른쪽 하단의 B점에 도달할 수도 있다.지나가는 길에 그는 네모난 칸의 수를 가져갈 수 있다(가져간 칸은 숫자 0으로 바뀔 것이다).이 사람은 A점에서 B점까지 모두 두 번 걸으며 이런 경로 두 개를 찾아내 얻은 수의 합이 가장 크다.
입력한 첫 번째 동작은 정수 N(N*N을 나타내는 네모난 그림)을 입력하고 그 다음 줄마다 세 개의 정수가 있으며 앞의 두 개는 위치를 나타내고 세 번째 수는 그 위치에 놓인 수입니다.별도의 행 0은 입력이 끝났음을 나타냅니다.
출력은 두 경로에서 얻은 가장 큰 합을 나타내는 정수만 출력할 수 있다.
샘플 입력 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
샘플 출력 67
사고방식은 네 개의 dp수 그룹을 구축하여 두 사람이 각각 (x1, y1)(x2, y2) 두 개의 소득권치로 간주하고 dp가 점차적으로 추진하면 된다.
코드 구현
#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=15;
const int M=10005;
const int INF=0x3f3f3f3f;
const ull sed=31;
const ll mod=(1ll<<32);
const double eps=1e-8;
typedef pair<int,int>P;
typedef pair<double,double>Pd;

int dp[N][N][N][N];
int ar[4][4]={{1,0,1,0},{1,0,0,1},{0,1,1,0},{0,1,0,1}};
int mp[N][N],n;

int main()
{
    scanf("%d",&n);
    int u,v,w;
    while(~scanf("%d%d%d",&u,&v,&w) && u&& v&&w) mp[u][v]=w;
    for(int x1=1;x1<=n;x1++)
    {
        for(int y1=1;y1<=n;y1++)
        {
            for(int x2=1;x2<=n;x2++)
            {
                for(int y2=1;y2<=n;y2++)
                {
                    int temp=0;
                    for(int i=0;i<4;i++)
                    {
                        int ax1=x1-ar[i][0],ay1=y1-ar[i][1],ax2=x2-ar[i][2],ay2=y2-ar[i][3];
                        temp=max(temp,dp[ax1][ay1][ax2][ay2]);
                    }
                    dp[x1][y1][x2][y2]=max(temp,dp[x1][y1][x2][y2]);
                    dp[x1][y1][x2][y2]+=mp[x1][y1];
                    if(x1!=x2 && y1!=y2) dp[x1][y1][x2][y2]+=mp[x2][y2];
                }
            }
        }
    }
    printf("%d
",dp[n][n][n][n]);
    return 0;
}
Docker×Laravel×Vue.js에서 browserSync를 사용하다가 빠져서 그 처리 방법을 남겼어요!!!
[SSAC X 코딩온] (2021.10.21) Node.js 입문 수업 2일차

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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