menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】DP——关路灯
2020-05-16 | 【OI】 | 暂无评论 | 70 次阅读 | 129字

    好,我们接着下一题。题目链接放在这了:
https://www.luogu.com.cn/problem/P1220
    首先,我们先推出转移方程。转移方程如下:

//我们将f[i][j][k]设置成已经关掉i->j的灯时最小功耗。
//其中,若k=0,则此时人站在最左边,也就是i
//如果k=1,则此时人站在最右边,也就是j
//那么,转移方程如下:
f[i][j][0]=min(f[i+1][j][0]+(s[i+1]-s[i])*(sum[i]+sum[n]-sum[j]),f[i+1][j][1]+(s[j]-s[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][1]=min(f[i][j-1][0]+(s[j]-s[i])*(sum[i-1]+sum[n]-sum[j-1]),f[i][j-1][1]+(s[j]-s[j-1])*(sum[i-1]+sum[n]-sum[j-1]));

    没错,转移方程非常长。最后,将转移方程写入代码,最终形态如下:

#include <bits/stdc++.h>
using namespace std;
int f[55][55][2];
int s[55],sum[55];
int n,c,w;
int main()
{
    cin>>n>>c;
    memset(f,0x7F,sizeof(f));
    f[c][c][0]=f[c][c][1]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i]>>w;
        sum[i]=sum[i-1]+w;
    }
    for(int l=2;l<=n;l++)
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+l-1;
            f[i][j][0]=min(f[i+1][j][0]+(s[i+1]-s[i])*(sum[i]+sum[n]-sum[j]),f[i+1][j][1]+(s[j]-s[i])*(sum[i]+sum[n]-sum[j]));
            f[i][j][1]=min(f[i][j-1][0]+(s[j]-s[i])*(sum[i-1]+sum[n]-sum[j-1]),f[i][j-1][1]+(s[j]-s[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
        }
    cout<<min(f[1][n][1],f[1][n][0]);
    return 0;
}


耶(^-^)V耶
    好,本题记录到这里,我们下一题见。

None
发表评论
暂无评论
textsms
account_circle
email
link
arrow_forward 下一篇