洛谷 P1220 关路灯

题目传送门

解题思路:

f[i][j][0]表示i~j区间的灯全部被关了,当前站在i.

f[i][j][1]表示i~j区间的灯全部被关了,当前站在j.

剩下在代码里.

AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int n,c,a[51],v[51],sum[51],f[51][51][2];

int main() {
    scanf("%d%d",&n,&c);
    for(int i = 1;i <= n; i++) {
        scanf("%d%d",&a[i],&v[i]);
        sum[i] = sum[i-1] + v[i];
    }
    memset(f,0x3f3f,sizeof(f)); 
    f[c][c][1] = f[c][c][0] = 0;
    for(int len = 1;len < n; len++)
        for(int i = 1,j = len + i;j <= n; i++,j++) {
            f[i][j][0] = min(f[i+1][j][0] + (a[i+1] - a[i]) * (sum[i] + sum[n] - sum[j]),f[i+1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i]));
            //从i+1走过来,或从j走过来关i 
            f[i][j][1] = min(f[i][j-1][1] + (a[j] - a[j-1]) * (sum[i-1] + sum[n] - sum[j-1]),f[i][j-1][0] + (a[j] - a[i]) * (sum[i-1] + sum[n] - sum[j-1]));
            //从j-1走过来,或从i走过来关j 
        }
    printf("%d",min(f[1][n][0],f[1][n][1]));
    return 0;
}