题解 P3080 【[USACO13MAR]牛跑The Cow Run】

ysj1173886760 · 2018-09-30 07:26:29 · 题解

简单的区间dp

可以先做关路灯，在做这道题，双倍经验。

dp[i][j][0/1]表示当前已经套完了i到j的牛，然后 第三维表示在左边还是在右边。

那么对于每次处理完区间i~j,我们如何递推出别的状态呢？

我们下一步可以选择去i-1，也就是下一步到dp[i-1][j],

或者选择去j+1,到dp[i][j+1]。

对于每一个当前的状态，fj可能在左边或者右边，也就是dp[i][j][1]或者dp[i][j][0],每一个又有两种转移方案。

两种状态一起处理就好。

我把n个点拆成了n+1个点，找到0点，设为c，令dp[c][c][0]=dp[c][c][1]=0,其他的都为inf， 两重循环转移即可，复杂度O(n^2)

主要是代码比较简洁，无压行30行，所以我想发这个题解。qaq

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

const int maxn=1e3+10;

int n;
int pos[maxn],dp[maxn][maxn][2];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>pos[i];               //读入 
    sort(pos+1,pos+1+n);                            //排个序 
    int c=lower_bound(pos+1,pos+1+n,0)-pos;         //找到0点 
    memset(dp,0x3f,sizeof(dp));                     //初始化极大值 
    for(int i=n;i>=c;i--)pos[i+1]=pos[i];           //把零点以后的向右移一位，注意逆序 ，类比背包滚动数组。 
    pos[c]=0;   
    dp[c][c][0]=dp[c][c][1]=0;                      //初始化起点 
    for(int l=2;l<=n+1;l++)                         //开始区间dp，枚举区间长度 
        for(int i=1;i+l-1<=n+1;i++)                 //枚举左端点 
        {
            int j=i+l-1;                            //计算右端点 
            dp[i][j][0]=min(dp[i+1][j][0]+(pos[i+1]-pos[i])*(n-j+i+1),dp[i+1][j][1]+(pos[j]-pos[i])*(n-j+i+1));//n-j+i+1为区间大小，也就是牛的个数. 
            dp[i][j][1]=min(dp[i][j-1][1]+(pos[j]-pos[j-1])*(n-j+i+1),dp[i][j-1][0]+(pos[j]-pos[i])*(n-j+i+1));
        }
    cout<<min(dp[1][n+1][1],dp[1][n+1][0]);         //最终可能在左边或者右边. 
    return 0;
}