题解

104 条题解

  • 10
    @ 2017-05-08 09:10:20
    /*
    经典好题~一个dp必学题叭~~
    首先我们要想怎么样才能完整表示一个状态~
    我们可以看到的
    如果去关灯关掉了区间[l,r]的灯
    那么最后关的一盏不是l就是r
    所以我们可以想到用这样一个状态表示
    f[l][r][k]表示关掉区间[l,r]的所有灯所需要的最小代价
    其中k=0表示现在人在l即最后关的灯是l
    k=1表示现在人在r即最后关的是r这盏灯
    这样就设计出了一个正确无误的状态
    先考虑初值
    f[i][i]就是从起始位置直接到i开i灯的代价
    那么我们来考虑状态转移
    我们知道f[l][r][0]表示的是最后关掉了l这盏灯使得[l,r]全部都关了
    那么对应的上一个状态必然是已经关掉了[l+1,r]区间所有的灯
    那么我们就要考虑到到底是f[l+1][r][0]转移过来更优还是f[l+1][r][1]更优
    即考虑到了左右两种完全的情况
    那么很容易有状态转移
    f[i][j][0]=min(f[i+1][j][0]+(sump-(s[i+1][j]))*getd(i,i+1),
                   f[i+1][j][1]+(sump-(s[i+1][j]))*getd(i,j));
    其中我们已经预处理出sump表示所有灯总功率
    s[i]表示1...i的所有灯的功率然后用前缀和可以算出s[i+1][j]
    这个转移仔细理解一下就好了
    同理就可以得出f[i][j][1]的转移
    递推的时候外层循环枚举长度内层循环枚举起点
    最后取f[1][n][0]和f[1][n][1]的更优值就好了~
    时间复杂度O(n^2)
    可以直接秒杀~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=52;
    int f[MAXN][MAXN][2];
    int d[MAXN];
    int s[MAXN];
    int sump;
    int n,poss;
    
    void init()
    {
        int p;
        scanf("%d%d",&n,&poss);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&d[i],&p);
            s[i]=s[i-1]+p;  sump+=p;
        }
    }
    
    inline int getd(int x,int y)
    {
        return abs(d[x]-d[y]);
    }
    
    void DP()
    {
        memset(f,0x37,sizeof(f));
        for(int i=1;i<=n;i++)
            f[i][i][0]=f[i][i][1]=abs(d[i]-d[poss])*sump;
        for(int l=2;l<=n;l++)
            for(int i=1;i<=n&&i<=n-l+1;i++)
            {
                int j=i+l-1;
                f[i][j][0]=min(f[i+1][j][0]+(sump-(s[j]-s[i]))*getd(i,i+1),
                               f[i+1][j][1]+(sump-(s[j]-s[i]))*getd(i,j));
                f[i][j][1]=min(f[i][j-1][0]+(sump-(s[j-1]-s[i-1]))*getd(i,j),
                               f[i][j-1][1]+(sump-(s[j-1]-s[i-1]))*getd(j-1,j));
            }
        cout<<min(f[1][n][0],f[1][n][1])<<endl;
    }
    
    int main()
    {
        init();
        DP();
    }
    
  • 1
    @ 2019-03-08 23:08:09

    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int MAXM=60;
    int a[MAXM],b[MAXM],sum[MAXM],n,m,c;
    int f[MAXM][MAXM][2];
    int min(int a,int b)//这一点希望大家注意:最好max和min函数自己写,会有效的加快程序速度
    {return a<b?a:b;}
    int max(int a,int b)
    {return a>b?a:b;}
    int main()
    {
    scanf("%d%d",&n,&c);
    memset(f,127,sizeof(f));//赋成极大值防止后面的min出问题
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]),sum[i]=sum[i-1]+b[i];
    f[c][c][0]=f[c][c][1]=0;//瞬间被关(初始化)
    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]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]),//继续走下去会更快吗?
    f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));//还是从j点折返回来会更快?(此时假设[i+1][j]被关,i亮,从j端点往回赶去关i)
    //要注意的一点是sum[n]-(sum[j]-sum[i])是包括了i这一点的电能的,因为走过来的过程中灯i也会耗电
    f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]),//同上
    f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
    }
    int ans=min(f[1][n][0],f[1][n][1]);
    printf("%d",ans);
    return 0;
    }

  • 1
    @ 2017-08-13 22:21:41
  • 1
    @ 2017-08-13 22:21:37
  • 1
    @ 2016-08-09 08:28:56
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    
    typedef long long lg;
    #define MAXX 200
    #define min(a,b) (a<b?a:b)
    //#define OPENFILE
    
    struct Data
    {
        int x,v;
    }a[MAXX];
    
    lg sum[MAXX],f[MAXX][MAXX][2];
    int n,c;
    
    bool comp(const Data a,const Data b)
    {
        if(a.x==b.x)
            return a.v<b.v;
        return a.x<b.x;
    }
    
    int main(int argc, char** argv)
    {
    #  ifdef OPENFILE
       freopen("data.in","r",stdin);
    #  endif
       scanf("%d%d",&n,&c);
       for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].v);
       std::sort(a+1,a+n+1,comp);
       for(int i=1;i<=n;i++)
         sum[i]=sum[i-1]+a[i].v;
       for(int i=1;i<=n;i++)
         f[i][i][0]=f[i][i][1]=abs(a[i].x-a[c].x)*sum[n];
        //std::cout<<sum[1]<<"\n";
       for(int j=2;j<=n;j++)
         for(int i=1;i+j-1<=n;i++)
         { 
            int k=i+j-1;
            lg summ=sum[n]-sum[k]+sum[i];
            f[i][k][0]=min(f[i+1][k][0]+abs(a[i].x-a[i+1].x)*summ,f[i+1][k][1]+abs(a[k].x-a[i].x)*summ);
            summ=sum[n]-sum[k-1]+sum[i-1];
            f[i][k][1]=min(f[i][k-1][1]+abs(a[k-1].x-a[k].x)*summ,f[i][k-1][0]+abs(a[i].x-a[k].x)*summ);
         }
       printf("%ld",(min(f[1][n][0],f[1][n][1])));
       return 0;
    }
    
  • 1
    @ 2016-04-06 17:56:34

    感谢S.Y.F大牛的题解。说明2点:
    1. 所有数据中距离都是排好序的,不必特殊处理。
    2. 有人说第一个点有50个空行,需要特判,其实不必。

    f[l,r,k] 表示已经关掉[l,r]区间时最小总消耗。k=0表示人在 l 处;k=1表示人在 r 处

    \(
    f[l,r,0] = min \{ f[l+1,r,0] + (P-sum[l+1,r])*dist[l,l+1], f[l+1,r,1] + (P-sum[l+1,r])*dist[l,r] \} \\
    f[l,r,1] = min \{ f[l,r-1,1] + (P-sum[l,r-1])*dist[r-1,r], f[l,r-1,0] + (P-sum[l,r-1])*dist[l,r] \}
    \)

    其中 P 是所有灯的功率之和,sum[l,r]=区间[l,r]内灯的功率之和,dist[l,r]=l到r的距离。
    sum和dist都预处理出来即可。
    放一段核心代码(pos 是人的初始位置)

    for(l=pos; l>=1; l--){
    for(r=pos; r<=num; r++){
    if(l < pos)
    f[l][r][0] = Min(f[l+1][r][0] + (P-sum[l+1][r])*dist[l][l+1], f[l+1][r][1] + (P-sum[l+1][r])*dist[l][r]);
    if(r > pos)
    f[l][r][1] = Min(f[l][r-1][1] + (P-sum[l][r-1])*dist[r-1][r], f[l][r-1][0] + (P-sum[l][r-1])*dist[l][r]);
    }
    }

  • 1
    @ 2016-01-21 22:40:25

    #include<iostream>
    using namespace std;
    int f[57][57][2] = {0}, w[57][57] = {0}, l[57][57] = {0};
    int n, m, wh[57], p[57];
    int sum;
    void pre(int a, int b)
    {
    for(int i = a; i <= b; i++)
    {
    w[a][b] += p[i];
    }
    l[a][b] = wh[b] - wh[a];
    }

    int main()
    {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    cin >> wh[i] >> p[i];
    for(int i = 1; i <= n; i++)
    for(int j = i; j <= n; j++)
    pre(i, j);
    sum = w[1][n];
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    for(int k = 0; k <= 1; k++)
    f[i][j][k] = 10000000;
    f[m][m][1] = 0; f[m][m][0] = 0;

    for(int k = 1; k <= n; k++)
    {
    for(int i = 1; i <= n - k; i++)
    {
    int j = i + k;
    f[i][j][0] = min(f[i + 1][j][0] + (sum - w[i + 1][j]) * l[i][i + 1], f[i + 1][j][1] + (sum - w[i + 1][j]) * l[i][j]);
    f[i][j][1] = min(f[i][j - 1][1] + (sum - w[i][j - 1]) * l[j - 1][j], f[i][j - 1][0] + (sum - w[i][j - 1]) * l[i][j]);
    // cout << f[i][j][0] << " " << f[i][j][1] << endl;
    }
    }
    cout << min(f[1][n][0], f[1][n][1]);
    return 0;
    }
    参考楼上大神(们)的想法。。。因为没有c++的,冒昧发一篇,希望有用

  • 0
    @ 2020-12-11 21:27:25

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;

    const int MAXN=52;
    int f[MAXN][MAXN][2];
    int d[MAXN];
    int s[MAXN];
    int sump;
    int n,poss;

    void init()
    {
    int p;
    scanf("%d%d",&n,&poss);
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d",&d[i],&p);
    s[i]=s[i-1]+p; sump+=p;
    }
    }

    inline int getd(int x,int y)
    {
    return abs(d[x]-d[y]);
    }

    void DP()
    {
    memset(f,0x37,sizeof(f));
    for(int i=1;i<=n;i++)
    f[i][i][0]=f[i][i][1]=abs(d[i]-d[poss])*sump;
    for(int l=2;l<=n;l++)
    for(int i=1;i<=n&&i<=n-l+1;i++)
    {
    int j=i+l-1;
    f[i][j][0]=min(f[i+1][j][0]+(sump-(s[j]-s[i]))*getd(i,i+1),
    f[i+1][j][1]+(sump-(s[j]-s[i]))*getd(i,j));
    f[i][j][1]=min(f[i][j-1][0]+(sump-(s[j-1]-s[i-1]))*getd(i,j),
    f[i][j-1][1]+(sump-(s[j-1]-s[i-1]))*getd(j-1,j));
    }
    cout<<min(f[1][n][0],f[1][n][1])<<endl;
    }

    int main()
    {
    init();
    DP();
    }

  • 0
    @ 2018-08-16 16:58:12

    #include <iostream>
    #include <cstring>
    using namespace std;
    long long n,s,a[1001],w[1001];
    long long t[1001][1001],f[1001][1001][2];
    int main()
    {
    int i,j,l;
    cin>>n>>s;
    for(i=1;i<=n;i++)
    cin>>a[i]>>w[i];
    for(i=1;i<=n;i++)
    for(j=i;j<=n;j++)
    t[i][j]=t[i][j-1]+w[j];
    int sum=t[1][n];
    for(i=1;i<=n;i++)
    for(j=i;j<=n;j++)
    t[i][j]=sum-t[i][j];
    memset(f,1,sizeof f);
    f[s][s][0]=f[s][s][1]=0;
    for(l=2;l<=n;l++)
    for(i=1;i<=n-l+1;i++)
    {
    int j=i+l-1;
    f[i][j][0]=min(f[i+1][j][0]+t[i+1][j]*(a[i+1]-a[i]),f[i+1][j][1]+t[i+1][j]*(a[j]-a[i]));
    f[i][j][1]=min(f[i][j-1][1]+t[i][j-1]*(a[j]-a[j-1]),f[i][j-1][0]+t[i][j-1]*(a[j]-a[i]));
    }
    cout<<min(f[1][n][0],f[1][n][1]);
    return 0;
    }

  • 0
    @ 2018-07-11 23:08:59

    /*其实这道区间DP还是值得一做,经典题思考起来总是那么吃力却非常满足~~
    思路如下:
    对于左右区间DP,状态有俩种:
    A.向左 B.向右
    经过~~借鉴大佬后~~我~~们~~不妨用一个多维dp来储存状态:dp[i][j]k
    其中1为右位,0为左位
    对于dp[i][j]1可从dp[i+1][j]0
    和dp[i+1][j]1 ,最后注意的一点是i,j的顺序问题(这里就不再赘述)*/
    cpp
    #include<iostream>
    #include<cstring>
    #define M 60//大点
    using namespace std;
    int dp[M][M][2],e[M],d[M];
    int eng[M];
    int minx(int x,int y)
    {
    return x<y?x:y;
    }
    int main()
    {
    int n,c;
    ios::sync_with_stdio(false);//取消联系,飞的更快
    cin>>n>>c;
    memset(eng,0,sizeof(eng));
    memset(dp,127,sizeof(dp));//初始化
    dp[c][c][0]=dp[c][c][1]=0;
    for (register int i=1;i<=n;i++) {
    cin>>d[i]>>e[i];//e为消耗量,d为距离
    eng[i]=eng[i-1]+e[i];//用一个前缀和储存损失的能量
    }
    for (register int j=c;j<=n;j++)
    for (register int i=j-1;i>=1;i--)
    {
    int e1_go=(d[i+1]-d[i])*(eng[n]+eng[i]-eng[j]);//去的损失能量
    int e1_bk=(d[j]-d[i])*(eng[n]+eng[i]-eng[j]);//回的损失能量,下同
    int e2_go=(d[j]-d[j-1])*(eng[n]+eng[i-1]-eng[j-1]);
    int e2_bk=(d[j]-d[i])*(eng[n]+eng[i-1]-eng[j-1]);
    dp[i][j][0]=minx(dp[i+1][j][0]+e1_go,dp[i+1][j][1]+e1_bk);
    dp[i][j][1]=minx(dp[i][j-1][1]+e2_go,dp[i][j-1][0]+e2_bk);
    }
    int ans=minx(dp[1][n][0],dp[1][n][1]);//最后比较是在左端还是在右端更小
    cout<<ans;
    return 0;
    }

    蒟蒻程序,大佬指教
    ~~~·

  • 0
    @ 2017-12-09 19:30:19

    /*借鉴大佬的*/
    #include<bits/stdc++.h>
    using namespace std;
    int f[2017][2017],dp[2000][2000][3];
    int a[2017],b[2017],n,m,v=0,x,y,c;
    int main()
    {
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]),b[i]+=b[i-1];
    memset(dp,127,sizeof(dp));
    dp[c][c][0]=dp[c][c][1]=0;
    for(int i=c;i>=1;i--)
    for(int j=i+1;j<=n;j++)
    {
    dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1]-a[i])*(b[n]-(b[j]-b[i])));
    dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j]-a[i])*(b[n]-(b[j]-b[i])));
    dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j]-a[j-1])*(b[n]-(b[j-1]-b[i-1])));
    dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j]-a[i])*(b[n]-(b[j-1]-b[i-1])));
    }
    printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
    return 0;
    }

  • 0
    @ 2017-08-13 22:20:55
  • 0
    @ 2017-07-30 17:43:33
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    struct segment_tree_1
    {
        int l,r,mid,x;
    }st[2*64+2];
    
    int n,m;
    int a[51+1];
    int p[51+1];
    int f[51+1][51+1][1+1];
    
    void build_segment_tree_1(int now,int l,int r)
    {
        st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2;
        if (l<r)
        {
            if (l<=st[now].mid)
                build_segment_tree_1(now*2,l,st[now].mid);
            if (st[now].mid+1<=r)
                build_segment_tree_1(now*2+1,st[now].mid+1,r);
        }
        if (l==r)
            st[now].x=p[l];
        else
            st[now].x=st[now*2].x+st[now*2+1].x;
    }
    
    int sum_1(int now,int l,int r)
    {
        if (l>r)
            return 0;
        else if (st[now].l==l&&r==st[now].r)
            return st[now].x;
        else if (r<=st[now].mid)
            return sum_1(now*2,l,r);
        else if (st[now].mid+1<=l)
            return sum_1(now*2+1,l,r);
        else
            return sum_1(now*2,l,st[now].mid)+sum_1(now*2+1,st[now].mid+1,r);
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i],&p[i]);
        build_segment_tree_1(1,1,n);
        memset(f,oo_max,sizeof(f));
        f[m][m][0]=f[m][m][1]=0;
        for (int l=1;l<=n;l++)
            for (int i=1;i<=n-l+1;i++)
            {
                int j=i+l-1;
                f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i]));
                f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i]));
                f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[i]));
                f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[j-1]));
            }
        printf("%d\n",min(f[1][n][0],f[1][n][1]));
    }
    
    • @ 2017-07-30 17:44:29

      数据范围n<=50,数组最好开51,很H2O的题

    • @ 2017-07-30 17:48:54

      DP+Segment Tree来H2O一下

  • 0
    @ 2016-10-20 16:50:59
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int pos[51],w[51],sum[51][51];
    int f[51][51][2],tot;
    int main()
    {
        int n,c;
        cin>>n>>c;
        for(int i=1;i<=n;i++)
        {
            cin>>pos[i]>>w[i];
            tot+=w[i];
        }
        sum[1][1]=w[1];
        for(int i=2;i<=n;i++)
        {
            sum[1][i]=sum[1][i-1]+w[i];
            sum[i][i]=w[i];
        }
        for(int i=2;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                sum[i][j]=sum[i][j-1]+w[j];
        memset(f,127/3,sizeof f);
        f[c][c][0]=f[c][c][1]=0;
        int l,r;
        for(int i=c;i>=1;i--)
            for(int j=c;j<=n;j++)
            {
                
                if(i<c)
                    f[i][j][0]=min(f[i+1][j][0]+(pos[i+1]-pos[i])*(tot-sum[i+1][j]),f[i+1][j][1]+(pos[j]-pos[i])*(tot-sum[i+1][j]));
                if(c<j)
                    f[i][j][1]=min(f[i][j-1][1]+(pos[j]-pos[j-1])*(tot-sum[i][j-1]),f[i][j-1][0]+(pos[j]-pos[i])*(tot-sum[i][j-1]));
                l=f[i][j][0],r=f[i][j][1];
            }
        printf("%d",min(f[1][n][0],f[1][n][1]));
    }```
    感谢楼下大神题解
    
  • 0
    @ 2016-06-15 11:42:25

    记录信息
    评测状态 Accepted
    题目 P1150 关路灯
    递交时间 2016-06-15 11:41:49
    代码语言 C++
    评测机 ShadowShore
    消耗时间 0 ms
    消耗内存 580 KiB
    评测时间 2016-06-15 11:41:50
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    Accepted, time = 0 ms, mem = 580 KiB, score = 100
    代码
    #include<algorithm>
    #include<cctype>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<ctime>
    #include<iostream>
    #include<string>
    int f0[51][51],f1[51][51],s[51],p[51],n,m,temp;
    inline int min(int x,int y)
    {
    x-=y;return y+(x&(x>>31));
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
    scanf("%d%d",&p[i],&temp);
    s[i]=s[i-1]+temp;
    f0[1][i]=f1[1][i]=f0[i][0]=f1[i][0]=f0[i][n+1]=f1[i][n+1]=1000000000;
    }
    f0[1][m]=0;f1[1][m]=0;
    for(int i=2;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
    int &ff0=f0[i][j],&ff1=f1[i][j];
    if(j+1<=n)
    ff0=f0[i-1][j+1]+(s[j]+s[n]-s[j+i-1])*(p[j+1]-p[j]);
    if(j+i-1<=n)
    ff0=min(ff0,f1[i-1][j+i-1]+(s[j]+s[n]-s[j+i-1])*(p[j+i-1]-p[j]));
    if(j>=2)
    ff1=f1[i-1][j-1]+(s[j-i]+s[n]-s[j-1])*(p[j]-p[j-1]);
    if(j-i>=0)
    ff1=min(ff1,f0[i-1][j-i+1]+(s[j-i]+s[n]-s[j-1])*(p[j]-p[j-i+1]));
    }
    printf("%d",min(f0[n][1],f1[n][n]));
    return 0;
    }

  • 0
    @ 2016-03-22 21:40:41

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int N = 200 + 24;
    int n,m,sum[N];
    struct node
    {
    int a,b;
    }s[N];
    LL dp[N][N][2];
    LL dfs(int l, int r, int k)
    {
    if(dp[l][r][k] != -1)
    return dp[l][r][k];
    dp[l][r][k] = 1e16;
    if(l == r)
    return dp[l][r][k];
    dp[l][r][0] = min(dp[l][r][0],dfs(l+1,r,0) + (sum[l]-sum[0] + sum[n] - sum[r])*abs(s[l + 1].a - s[l].a) );
    dp[l][r][0] = min(dp[l][r][0],dfs(l+1,r,1) + (sum[l]-sum[0] + sum[n] - sum[r])*abs(s[r].a - s[l].a) );
    dp[l][r][1] = min(dp[l][r][1],dfs(l,r - 1,0) + (sum[l-1]-sum[0] + sum[n] - sum[r - 1])*abs(s[r].a - s[l].a) );
    dp[l][r][1] = min(dp[l][r][1],dfs(l,r - 1,1) + (sum[l-1]-sum[0] + sum[n] - sum[r - 1])*abs(s[r].a - s[r-1].a) );
    return dp[l][r][k];
    }
    int main()
    {
    #ifdef CDZSC_OFFLINE
    freopen("in.txt","r",stdin);
    #endif //CDZSC_OFFLINE
    while(~scanf("%d%d",&n,&m))
    {
    sum[0] = 0;
    memset(dp,-1,sizeof(dp));
    dp[m][m][0] = dp[m][m][1] = 0;
    for(int i = 1; i <= (n == 50 ? 100 : n); i++)//超有病的第一个数据,n == 50 时有100个输入。坑人!
    {
    scanf("%d%d",&s[i].a,&s[i].b);
    sum[i] = sum[i - 1] + s[i].b;
    }
    printf("%lld\n",min(dfs(1,n,0),dfs(1,n,1)));
    }
    }

  • 0
    @ 2015-08-04 16:50:40

    var n,c,i,j,sum:longint;
    m,w:array[0..1100] of longint;
    a,l,r:array[0..1005,0..1005] of longint;//a[i,j]表示除过从i到j之间的灯的功率,
    //l,r表示关完灯停留下哪个方向
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a) else exit(b);
    end;
    begin
    readln(n,c);
    sum:=0;
    for i:=1 to n do begin
    readln(m[i],w[i]);
    inc(sum,w[i]);
    end;
    for i:=1 to n do begin
    a[i,i]:=sum-w[i];
    for j:=i+1 to n do a[i,j]:=a[i,j-1]-w[j];
    end;
    for i:=c+1 to n do begin
    r[c,i]:=r[c,i-1]+(m[i]-m[i-1])*a[c,i-1];//从原点向右关灯后停在i位置
    l[c,i]:=r[c,i]+(m[i]-m[c])*a[c,i];//从原点向右关灯后返回到出发点c
    end;
    for i:=c-1 downto 1 do begin
    l[i,c]:=l[i+1,c]+(m[i+1]-m[i])*a[i+1,c];//从原点向左关灯后停在i位置
    r[i,c]:=l[i,c]+(m[c]-m[i])*a[i,c];//向左关灯后返回到出发点s
    end;
    for i:=c-1 downto 1 do
    for j:=c+1 to n do begin
    r[i,j]:=min(r[i,j-1]+(m[j]-m[j-1])*a[i,j-1],l[i,j-1]+(m[j]-m[i])*a[i,j-1]);
    l[i,j]:=min(l[i+1,j]+(m[i+1]-m[i])*a[i+1,j],r[i+1,j]+(m[j]-m[i])*a[i+1,j]);
    end;
    writeln(min(l[1,n],r[1,n]));
    end.

  • 0
    @ 2013-10-26 22:30:39

    这是我vj第一道交了三次才过的题目。一般都是一次AC的,而且这道题目改了我大半天。
    有以下几个原因:
    这种DP很经典,以前也看到过类似的一题,但没这么复杂,原来那题没有功率,只要考虑距离就行。
    虽然如此,但当时对于DP方程的含义理解还是出了些问题;不过,查漏补缺本来就是好事,写个题解,就是为了加深影响,防止下次再出错误。

    首先,要明确,由于老头从中间开始,左右开始按灭灯,所以按灭的灯肯定是连续的。
    即如果我当前在第5个位置,起始点在3,那第4盏灯肯定也是灭的。
    这就启示我们,可以只枚举当前位置,和一共按灭的灯来初步确定方程f[i,j]:=f[i-1,j±i]+num(j,j±i);
    为了方便起见,可以定义f[i,j,k],表示已经按灭i栈灯,已按灭的连续的灯的起点j,显然这样就能确定f[j,j+i-1]这个区间了,再用k表示老头处于的位置,0表示在区间的左端,1表示在区间的右端。这样就省去了不少繁琐的递推过程,使问题简化。

    然后在考虑有fi,j可以推出那些状态。很显然,如果我要向左走,就能推出f[i+1,j-1]的区间;向右走,就能推出f[i+1,j](仔细推敲区间的表示方式,可以画图帮助理解).即3-4推出2-4或3-5;
    再把k加进去。如果k=0,那些向左走,距离就是a[j]-a[j-1];如果k=1,那么向左走,就是a[i+j-1]-a[j-1].向右走也是同理。就留给大家自行思考了。

    对于每次走的那段距离,即我上面讲的。都会消耗任何一盏没有被按没的灯的能量。而没有按灭的灯单位时间消耗能量的总和,就是全部的功率tot减去已经按灭的灯的功率。因为已经按灭的灯是一个连续的区间sum(j-j+i-1),可以先预处理好sum的值,然后直接计算。
    这样看来,方程似乎已经显而易见了: f[i+1,j-1,0]:=min(f[i,j,0]+(a[j]-a[j-1])*(tot-b[j+I-1]+b[j-1]),
    f[i,j,1]+(a[j+i-1]-a[j-1])*(tot-b[j+i-1]+b[j-1]));
    我的sum用前缀和的方式代替了,效果一样。上面一给出了想走左的方程,向右自行思考。
    最后的答案就在min(f[n,1,1],f[n,1,0]);至于边界和初始化,就不在多讲。

    如果你按我这样写,你会发现,连样例都过不去//我刚开始就是这样。
    经过F7的单步调试,发现:在计算f[i,m]时,状态的继承会有问题。显然除了起始点,f[i,m]的值肯定是maxlongint。
    所以应该把m这个点中间点删掉。其余照旧即可。

    剩下就只有细节问题了。
    DXE-SYF。

  • 0
    @ 2013-10-01 14:45:13

    哈哈,一遍AC了。DP:f【i,j,1(0)】表示以老头为中心右边关了i个,左边关了j个,且人在右边(左边)时的代价。
    可以证明,对于F[I,J]一定只有2种走法:一种是原本人在左边第j个灯跑到右边关第i个灯,一种是原本人在右边的第i-1个灯关掉
    第i个灯。以下是核心代码:
    if i-1>=0 then begin
    f[i,j,1]:=min(f[i,j,1],f[i-1,j,0]+(sum-sm(c-j,c+i-1))*(l[c+i]-l[c-j]));
    f[i,j,1]:=min(f[i,j,1],f[i-1,j,1]+
    (sum-sm(c-j,c+i-1))*(l[c+i]-l[c+i-1]));
    同理,当F[I,J,0]也可以这样。(sm是函数用来算左边第j个灯到右边第i个灯的消耗量,l是距离,代价就是两者相乘(不算被
    关掉的那个灯,因为老头走到以后才关掉它,之前也消耗的))。
    -L.G.S庆祝国庆节!

信息

ID
1150
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
1489
已通过
593
通过率
40%
被复制
7
上传者