【DP专题】——洛谷P1220关路灯

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int read(){
 4     int x=0,f=1;
 5     char c=getchar();
 6     while(!isdigit(c)){
 7         if(c==‘-‘) f=-1;
 8         c=getchar();
 9     }
10     while(isdigit(c)){
11         x=x*10+c-‘0‘;
12         c=getchar();
13     }
14     return x*f;
15 }
16 const int N=60;
17 int n,c;
18 int f[N][N][2];
19 int dis[N];
20 int v[N],sum[N];
21 int d(int i,int j){
22     return dis[j]-dis[i];
23 }
24 int val(int i,int j){
25     return sum[n]-sum[j]+sum[i-1];
26 }
27 int main(){
28     n=read();c=read();
29     for(int i=1;i<=n;i++){
30         dis[i]=read();
31         v[i]=read();
32         sum[i]=sum[i-1]+v[i];
33     }
34     memset(f,0x3f,sizeof(f));
35     f[c][c][1]=f[c][c][0]=0;
36     for(int i=2;i<=n;i++){
37         for(int j=1;j+i-1<=n;j++){//(i,j+i-1)
38             int k=j+i-1;
39             f[j][k][0]=min(f[j][k][0],min(f[j+1][k][0]+val(j+1,k)*d(j,j+1),f[j+1][k][1]+val(j+1,k)*d(j,k)));
40             f[j][k][1]=min(f[j][k][1],min(f[j][k-1][1]+val(j,k-1)*d(k-1,k),f[j][k-1][0]+val(j,k-1)*d(j,k)));
41         }    
42     }
43     printf("%d",min(f[1][n][0],f[1][n][1]));
44     return 0;
45 }