題目這麽H2O就算了,還卡讀入

#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[50+1];
int p[50+1];
int f[50+1][50+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()
{
    while (~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]));
    }
}

3 条评论

  • @ 2017-07-30 20:53:59

    是数据没有51但你f数组用到了51吧。
    还有为啥要写线段树啊直接前缀和不行吗

    • @ 2017-07-31 12:18:14

      數據不是51那f為啥會用到了51?

    • @ 2017-07-31 12:19:50

      我寫綫段樹只是練練手

    • @ 2017-07-31 12:23:13

      哦,我知道了

      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]));
      
  • @ 2017-07-30 17:46:50

    好吧是數據範圍51,寫一個50來坑我
    AC

    #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 14:32:11

    RE

  • 1

信息

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