P1220关路灯

NOIP2018将至,于是我到洛谷上准备开始刷动归题,然而看了发现自己都不会
考虑到题中的N<=50,因此我们可以认为这是一道多维动归
在看到只在一条直线上动归,因此可以得知这是区间动归
我们用dp[i][j][k]来表示老张已经关了i-j的灯并且此时在一个端点上(k=0在i,k=1在j)
每个状态可以从左右两边走来进行转移
因此转移方程并不难得出
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=55;
int n,c;
int loc[maxn],p[maxn];
int dp[maxn][maxn][2];

int cal(int i,int j,int l,int r){
return(loc[j]-loc[i])*(p[l]+p[n]-p[r-1]);
}

int main(){
cin>>n>>c;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
loc[i]=a;
p[i]=p[i-1]+b;
}
dp[c][c][0]=dp[c][c][1]=0;
for(int j=c;j<=n;j++){
for(int i=j-1;i>=1;i--){
dp[i][j][0]=min(dp[i+1][j][0]+cal(i,i+1,i,j+1),dp[i+1][j][1]+cal(i,j,i,j+1));
dp[i][j][1]=min(dp[i][j-1][0]+cal(i,j,i-1,j),dp[i][j-1][1]+cal(j-1,j,i-1,j));
}
}
cout<<min(dp[1][n][0],dp[1][n][1]);
}