【luogu1220】关路灯 [动态规划区间dp]

朴灿烈づ我的快乐病毒、 2021-11-16 05:40 281阅读 0赞

[P1220 关路灯][P1220]

一道区间dp

先预处理出关掉了第i~j盏灯时的功率

然后f\[i\]\[j\]\[0/1\]表示关到灯i~j此时在左边(0)或右边(1)时最小的花费

有点像[\[HNOI2010\]合唱队][HNOI2010] 这题也是三维

#include<bits/stdc++.h>
    using namespace std;
    #define Max(x,y) (x)>(y)?(x):(y)
    #define Min(x,y) (x)>(y)?(y):(x)
    #define ll long long
    #define rg register
    const int N=100+5,M=1000000+5,inf=0x3f3f3f3f,P=19650827;
    int n,s,sum=0,pos[N],w[N],f[N][N][2],t[N][N];
    template <class t>void rd(t &x){
        x=0;int w=0;char ch=0;
        while(!isdigit(ch)) w|=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=w?-x:x;
    }
    
    int main(){
        //freopen("in.txt","r",stdin);
        rd(n),rd(s);
        for(int i=1;i<=n;++i) rd(pos[i]),rd(w[i]),sum+=w[i];
        for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j) t[i][j]=t[i][j-1]+w[j];
        for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j) t[i][j]=sum-t[i][j];
        memset(f,inf,sizeof(f));
        f[s][s][0]=f[s][s][1]=0;
        for(int l=2;l<=n;++l)//枚举长度 
        for(int i=1,j;i<=n-l+1;++i){
        //枚举左端点
            j=l+i-1;
            f[i][j][0]=Min(f[i+1][j][0]+t[i+1][j]*(pos[i+1]-pos[i]),f[i+1][j][1]+t[i+1][j]*(pos[j]-pos[i]));
            f[i][j][1]=Min(f[i][j-1][1]+t[i][j-1]*(pos[j]-pos[j-1]),f[i][j-1][0]+t[i][j-1]*(pos[j]-pos[i]));
        }
        printf("%d",Min(f[1][n][0],f[1][n][1]));
        return 0;
    }

转载于:https://www.cnblogs.com/lxyyyy/p/11201541.html

[P1220]: https://www.luogu.org/problemnew/show/P1220
[HNOI2010]: https://www.luogu.org/problemnew/show/P3205

发表评论取消回复

表情：

评论列表（有 0 条评论，281人围观）

还没有评论，来说两句吧...

相关阅读

相关 uva 1220 - Party at Hali-Bula 【入门树形dp】

题目：uva 1220 - Party at Hali-Bula 题意：一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，

Dear 丶/ 2022年08月13日 11:43/ 0 赞/ 287 阅读

相关 NBUT - 1220 SPY

题目衔接：[https://ac.2333.moe/Problem/view.xhtml?id=1220][https_ac.2333.moe_Problem_view.xht

快来打我*/ 2022年02月23日 05:26/ 0 赞/ 191 阅读

相关 UVa 1220 Party at Hali-Bula （树形DP，最大独立集）

题意：公司有 n 个人形成一个树形结构，除了老板都有唯一的一个直系上司，要求选尽量多的人，但不能同时选一人上和他的直系上司，问最多能选多少人，并且是不是唯一的方案。分

向右看齐/ 2021年12月18日 07:39/ 0 赞/ 222 阅读

相关洛谷P1220 关路灯【区间dp】

题目：[https://www.luogu.org/problemnew/show/P1220][https_www.luogu.org_problemnew_show_P12

我就是我/ 2021年12月12日 15:43/ 0 赞/ 279 阅读

相关 [树形dp] Luogu P4516 潜入行动

题目描述外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，`JYY` 已经联系好了黄金舰队，打算联合所有 `JSOIer` 抵御外星人的进攻。在黄金舰队就

电玩女神/ 2021年12月03日 22:51/ 0 赞/ 227 阅读

相关 Luogu3214 HNOI2011 卡农组合、DP

[传送门][Link 1] -------------------- 火题qwq 我们需要求的是满足元素个数为\\(M\\)、元素取值范围为\\(\[1,2^n-1\]\

客官°小女子只卖身不卖艺/ 2021年11月26日 09:40/ 0 赞/ 192 阅读

相关【luogu3174】 [HAOI2009]毛毛虫 [动态规划树形dp]

[3174 \[HAOI2009\]毛毛虫][3174_HAOI2009] 求一条链链上的节点和与链上节点相连的兄弟和最大在链上每个节点都被多算了一次所以初设为1 虽

亦凉/ 2021年11月16日 05:42/ 0 赞/ 272 阅读

相关【luogu1220】关路灯 [动态规划区间dp]

[P1220 关路灯][P1220] 一道区间dp 先预处理出关掉了第i~j盏灯时的功率然后f\[i\]\[j\]\[0/1\]表示关到灯i~j此时在左边(0)或右边(

朴灿烈づ我的快乐病毒、/ 2021年11月16日 05:40/ 0 赞/ 282 阅读

相关 luogu P2014 选课（树形dp）

[传送门][Link 1] 题意：现在有很多门课程，但是每门课程都会依赖某些其他的课程（即学了第\\(a\_i\\)门课程之后才能学习第\\(a\_\{i+1\}\\

女爷i/ 2021年11月05日 13:16/ 0 赞/ 390 阅读

相关 luogu P3146 （区间dp）

[传送门][Link 1] 题意：有一行格子，每个格子都有一个数值，如果相邻两个格子相同的话，可以合并成一个新的格子，新的格子的值为原来的值+1。现在问你通过不断的合

叁歲伎倆/ 2021年11月01日 09:10/ 0 赞/ 526 阅读