nyoj304 에너지 절약 동태 기획

이 문제는 오랫동안 스스로 생각해 보았지만 상태 이동 방정식을 생각해 내지 못했는데, 일깨워 주고 나서야 비로소 크게 깨달았다.이것은 구간형 DP입니다. 먼저 문을 열고 어떻게 저장되는지 봅시다. d[i][j][0]가 저장된 상태는 i에서 j까지 모든 불이 꺼졌고 로봇이 i점에 있을 때 소모하는 최소 출력입니다.d[i][j][1]은 i에서 j까지 모든 불이 꺼졌고 j점에 있을 때 소모되는 최소 출력을 의미한다.d[i][j][0] 구간(i, j)의 불이 모두 꺼졌고 로봇이 i점에 위치하고 있다. 이전 단계는 j점에서 오거나 i+1점에서 왔을 수도 있다. 두 가지 이전 상태가 있는데 그것이 바로 d[i][j][0]=min(d[i+1][j][0]+(로봇이 i+1에서 i점까지 걸어오는 동안 남은 불이 소모하는 출력), d[i+1][j]+(j점에서 i점까지 걸어가는 동안 나머지 꺼지지 않은 불이 소모하는 출력)이다.마찬가지로 d[i][j][1]=min(d[i][j-1][0]+(i점에서 j점까지 소모하는 출력), d[i][j-1][1]+(j-1에서 j점까지 소모하는 출력)).

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

//l、r                 ，st      ，w[i]      i      
int l, r, n, st, sum, w[1005], d[1005][1005][4];
void dp()
{
    for(int i = 1; i <= (r - l); i++)//     i    
    {
        for(int j = l; j <= (r-i); j++)
        {
            //       d[i][i+j][0]
            sum = d[j+1][j+i][2];
            //         ，                   
            if(sum != -1)
            {
                d[j][i+j][2] = d[j+1][i+j][2] - w[j];//            

                //          、        ，          >=0 
                if(d[j+1][j+i][0] >= 0 && d[j+1][j+i][1] >= 0)
                {
                    if(d[j+1][j+i][0] + sum < d[j+1][j+i][1] + i*sum)
                        d[j][i+j][0] = d[j+1][i+j][0] + sum;
                    else
                        d[j][i+j][0] = d[j+1][i+j][1] + i*sum;
                }
                //               ，        
                else if(d[j+1][j+i][0] >= 0 || d[j+1][j+i][1] >= 0)
                {
                    if(d[j+1][j+i][0] >= 0)
                        d[j][i+j][0] = d[j+1][i+j][0] + sum;
                    else
                        d[j][i+j][0] = d[j+1][i+j][1] + i*sum;
                }
            }
            //       d[j][j+i][1]
            sum = d[j][i+j-1][2];
            if(sum != -1)
            {
                d[j][i+j][2] = d[j][i+j-1][2] - w[i+j];
                if(d[j][i+j-1][0] >= 0 && d[j][i+j-1][1] >= 0)
                {
                    if(d[j][i+j-1][0] + i*sum < d[j][i+j-1][1] + sum)
                        d[j][i+j][1] = d[j][i+j-1][0] + i*sum;
                    else
                        d[j][i+j][1] = d[j][i+j-1][1] + sum;
                }
                else if(d[j][i+j-1][0] >= 0 || d[j][i+j-1][1] >= 0)
                {
                    if(d[j][j+i-1][0] >= 0)
                        d[j][i+j][1] = d[j][i+j-1][0] + i*sum;
                    else
                        d[j][i+j][1] = d[j][i+j-1][1] + sum;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        memset(w, 0, sizeof(w));
        memset(d, -1, sizeof(d));//         -1，       
        scanf("%d", &st);
        sum = 0;
        l = 10e5;
        r = 0;
        for(int i = 1; i <= n; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            w[a] = b;
            sum += b;//  sum         ，         
            if(i == st)
            {
                sum -= b;
                st = a;
            }
            if(a < l)
                l = a;
            if(a > r)
                r = a;
        }
        //d[i][j][2]     i j              
        d[st][st][0] = d[st][st][1] = 0;
        d[st][st][2] = sum;
        dp();
        int ans = min(d[l][r][0], d[l][r][1]);
        printf("%d
", ans);
    }
    return 0;
}