UVA12991 Game Rooms (线性DP数列分段问题）

题目链接
题目大意：

总体思路：
f[k][i]表示第i层楼选择的是K的最小代价
最终的一段段连续的0区间加上连续1区间，0和1连续区间循环。如果[l, r]区间放乒乓球桌那么l-1和r+1就必须是游泳池。显然我们就不需要考虑去打乒乓球的人的贡献，因为他们自己所在的楼层就有其想要的设施；拥有的人分为两段贡献1~ (l+ r)>>1去l-1位置，(l+ r)>>1|1~r去r+1的位置。于是我们状态转移的时候就枚举以 ii 为右端点的极大连续段。转移方程就为

cost为[l, r]区间另一类运动爱好者对答案的贡献。

注意l=1&&r=n是不合法的状态要特判掉，因为题目要求要至少有一个乒乓球台和一个游泳池。

实现代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18;
int T;
int n;
ll x;
ll sum1[2][4005],sum2[2][4005];
ll f[2][4005];
//f[i][j]表示第j层选i的最小距离和，i=0表示选乒乓球，i=1表示选游泳池
ll cal1(int l,int r,int k){
    return 1ll*sum2[k^1][r]-sum2[k^1][l-1]-(l-1)*(sum1[k^1][r]-sum1[k^1][l-1]);
} 
ll cal2(int l,int r,int k){
    return 1ll*(r+1)*(sum1[k^1][r]-sum1[k^1][l-1])-(sum2[k^1][r]-sum2[k^1][l-1]);
}
ll cost(int l,int r,int k){
    if(l==1&&r==n) return INF;
    if(l==1) return cal2(l,r,k);
    if(r==n) return cal1(l,r,k);
    int mind=(l+r)>>1;
    return cal1(l,mind,k)+cal2(mind+1,r,k);
}
int main(){
    scanf(" %d",&T);
    for(int t=1;t<=T;t++){
        scanf(" %d",&n);
        for(int i=1;i<=n;i++){
            for(int j=0;j<2;j++){
                scanf(" %lld",&x);
                sum1[j][i]=sum1[j][i-1]+x;
                sum2[j][i]=sum2[j][i-1]+1ll*x*i;//注意这里会爆int
            }
        }
        f[0][0]=0; f[1][0]=0;
        for(int i=1;i<=n;i++){
            for(int k=0;k<2;k++){
                f[k][i]=INF;
                for(int j=0;j<i;j++){
                    f[k][i]=min(f[k][i],f[k^1][j]+cost(j+1,i,k));
                }
            }
        } 
        printf("Case #%d: %lld\n",t,min(f[0][n],f[1][n]));
    }
    return 0;
}