tyvj MM不哭

一时失言乱红尘 2021-12-12 06:35 216阅读 0赞

这道题是一个典型的区间类动态规划,与之类似的还有rqnoj的关灯问题~

这种题目的解法通常比较单一,但是比较难想出正确的解法,下面就是我的解法：

假设此时已经安慰好了第i个MM和第j个MM及其之间的所有MM。如果此时站在第i个MM所在的位置，用f\[i,j,0\]表示之后需要消耗的最小RP；如果此时站在第j个MM所在的位置，用f\[i,j,1\]表示在此之后需要消耗的最小RP。  
这里通过记忆化搜索实现  
下面附上核心代码

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #define zsz 200000000//注意最大值不要定小了,我刚开始定了100000000,结果有一组数据的最小值是110036500,WA了一次~~悲剧
    int n;
    int f[1005][1005][2];
    int w[1005],sum[1005],l[1005];
    int min(int a,int b)
    {
        return (a>b)?b:a;
    }
    int minn(int a,int b,int k)
    {
        if (a==0&&b==n) return 0;
        if (f[a][b][k]!=-1) return f[a][b][k];
        f[a][b][k]=zsz;
        if (k==0)
        {
                 if (a-1>=0) f[a][b][k]=min(f[a][b][k],minn(a-1,b,0)+(l[a]-l[a-1])*(sum[n]-sum[b]+sum[a-1]));
                 if (b+1<=n) f[a][b][k]=min(f[a][b][k],minn(a,b+1,1)+(l[b+1]-l[a])*(sum[a-1]+sum[n]-sum[b]));
        }
        if (k==1)
        {
                 if (a-1>=0) f[a][b][k]=min(f[a][b][k],minn(a-1,b,0)+(l[b]-l[a-1])*(sum[n]-sum[b]+sum[a-1]));
                 if (b+1<=n) f[a][b][k]=min(f[a][b][k],minn(a,b+1,1)+(l[b+1]-l[b])*(sum[n]-sum[b]+sum[a-1]));
        }
        return f[a][b][k];
    }
    int main()
    {
        freopen("zsz.in","r",stdin);
        freopen("zsz.out","w",stdout);
        int v;
        scanf("%d",&n);
        scanf("%d",&v);
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&l[i],&w[i]);
            sum[i]=sum[i-1]+w[i];
        }
        memset(f,-1,sizeof(f));//刚刚知道memset可以直接附上-1..   
        printf("%d\n",minn(v,v,0));
        return 0;
    }

转载于:https://www.cnblogs.com/foreverzsz/archive/2010/11/17/1879525.html