这道题是一道区间 dp 的题目
我们如何看出他是区间 dp?
因为他是在一条线上从小区间不断向大区间扩散, 长度不断增加, 所以大区间的答案一定是从小区间的答案更新而来
题目已知的信息有区间位置, 和功率和米数, 所以我们要从这些信息入手.
如何设计 dp 状态?
我们观察到我们需要保存小区间的答案, 所以我们前两维可以定位 i-j 区间都被关闭的最小功率, 但是这样显然还是不够的, 我们还要一种状态叫做向左向右.
所以我们可以设计第三维为在左端点和右端点, 根据他来更新之后向左和向右的答案.
消耗可以用作功率 * 米数, 我们还需要保存 sum 数组, 用来保存任意区间内在 1s 内消耗的功率, 这样就能更新所有状态
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=110;
- struct node{
- int p;
- int x;
- }s[N];
- int f[N][N][2];
- int sum[N][N];
- int main(){
- int n;
- int c;
- cin>>n>>c;
- int i;
- for(i=1;i<=n;i++){
- cin>>s[i].x>>s[i].p;
- }
- int j;
- for(i=1;i<=n;i++){
- sum[i][i]=s[i].p;
- for(j=i+1;j<=n;j++){
- sum[i][j]=sum[i][j-1]+s[j].p;
- }
- }
- memset(f,0x3f,sizeof f);
- f[c][c][0]=f[c][c][1]=0;
- int len;
- int l,r;
- for(len=2;len<=n;len++){
- for(l=1;l+len-1<=n;l++){
- r=l+len-1;
- f[l][r][0]=min(f[l+1][r][0]+(s[l+1].x-s[l].x)*(sum[1][l]+sum[r+1][n]),f[l+1][r][1]+(s[r].x-s[l].x)*(sum[1][l]+sum[r+1][n]));
- f[l][r][1]=min(f[l][r-1][1]+(s[r].x-s[r-1].x)*(sum[1][l-1]+sum[r][n]),f[l][r-1][0]+(s[r].x-s[l].x)*(sum[1][l-1]+sum[r][n]));
- }
- }
- cout<<min(f[1][n][0],f[1][n][1])<<endl;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3399172.html