NYOJ -304 절전 DP

 

에너지 절약

시간 제한: 1000ms | 메모리 제한: 65535KB
난이도
 
묘사
Dr.Kong이 디자인한 로봇 카드는 갈수록 똑똑해진다.최근 시정 회사는 카드에게 매일 아침 5시부터 ZK대로 오른쪽에 있는 모든 가로등을 끄는 임무를 맡겼다.
카도는 아침 5시가 되면 틀림없이 ZK 대로의 한 가로등 옆에 있을 것이다. 그리고 그는 불을 끄기 시작한다.모든 등은 일정한 출력을 가지고 로봇 카드는 자각적인 에너지 절약 의식을 가지고 불을 끄는 동안 ZK대로 오른쪽에 있는 모든 가로등의 소모 전력량이 가장 적기를 바란다.
로봇 카드는 1m/s의 속도로 걷는다.가령 불을 끄는 동작은 어떤 가로등을 통과할 때 불을 끄는 데 시간이 걸리지 않는다고 가정하면 된다.
프로그램을 작성하여 가로등 설정, 전구 출력과 로봇 카드가 많은 시작 위치에서 카드를 많이 끄는 동안 ZK대로의 모든 불이 소모하는 최소 에너지를 계산해 보세요.
 
입력
EOF를 입력으로 끝낸 여러 테스트 데이터가 있습니다.
그룹당 테스트 데이터 첫 줄: N은 ZK 대로 오른쪽 가로등의 수량을 나타낸다(2≤ N≤1000)
두 번째 줄: V는 로봇 카드가 불을 끄기 시작한 가로등 번호를 나타낸다.(1≤V≤N)
다음 N행에는 각 램프의 매개변수를 설명하기 위해 공백으로 구분된 두 개의 정수 D와 W가 포함됩니다.
D는 가로등과 ZK 대로의 시작점의 거리를 나타냅니다.
W는 전구의 전력, 즉 초당 이 전구가 소모하는 에너지의 수를 나타낸다.가로등은 순서대로 정해져 있다.
( 0≤D≤1000, 0≤W≤1000 )
출력
에너지를 소모하는 합의 최소값인 정수를 출력하다.200000000 미만의 결과 확인
샘플 입력

4 

3

2 2

5 8

6 1

8 7

샘플 출력

56

  ：

#include<stdio.h>

#include<string.h>

struct node

{

    int d;

    int w;

}f[1001];

int dp[1001][1001][2];

int w[1001][1001];

int min(int a,int b)

{

    return a<b?a:b;

}

int main()

{

    int n,v,fw,i,j;

    while(scanf("%d%d",&n,&v)!=EOF)

    {

        fw=0;

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

        {

            scanf("%d%d",&f[i].d,&f[i].w);

            fw+=f[i].w;

        }

    //    memset(dp,0,sizeof(dp));

        memset(w,0,sizeof(w));

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

            for(j=i;j<=n;++j)

                w[i][j]=w[i][j-1]+f[j].w;

        for(i=v-1;i>0;i--)

        {

            dp[i][v][0]=dp[i+1][v][0]+(fw-w[i+1][v])*(f[i+1].d-f[i].d);

            dp[i][v][1]=dp[i][v][0]+(fw-w[i][v])*(f[v].d-f[i].d);

        }

        for(i=v+1;i<=n;i++)

        {

            dp[v][i][1]=dp[v][i-1][1]+(fw-w[v][i-1])*(f[i].d-f[i-1].d);

            dp[v][i][0]=dp[v][i][1]+(fw-w[v][i])*(f[i].d-f[v].d);

        }

        for(i=v-1;i>0;i--)

            for(j=v+1;j<=n;++j)

            {

                dp[i][j][0]=min(dp[i+1][j][0]+(fw-w[i+1][j])*(f[i+1].d-f[i].d),

                                    dp[i+1][j][1]+(fw-w[i+1][j])*(f[j].d-f[i].d));

                dp[i][j][1]=min(dp[i][j-1][0]+(fw-w[i][j-1])*(f[j].d-f[i].d),

                                    dp[i][j-1][1]+(fw-w[i][j-1])*(f[j].d-f[j-1].d));

            }

        printf("%d
",min(dp[1][n][0],dp[1][n][1]));

    }

    return 0;

}