题意：

有n（4000）层楼，每层楼有1e9个人，每个人都有自己喜欢的一种运动（一共有两种），每层楼都可以开两种运动馆其中之一

如果当前开了a馆，则这一层喜欢b运动的人都要移动到最近的开b运动的楼层，代价是楼层差，让你合理安排，问你最小的代价

思路：

看http://blog.csdn.net/kirito_acmer/article/details/49700065这个代码注释吧，感觉自己肯定是想不出来的

#include<iostream>  
#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
#include<math.h>  
#include<vector>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<string>  
#include<algorithm>  
using namespace std;  
typedef long long ll;  
#define inf 0x7fffffff  
#define maxn 4050  
ll a[maxn],b[maxn];  
ll sum[maxn][2];//sum[i][u]表示前i层楼，性别为u的总人数  
ll dsum[maxn][2];//dsum[i][u]表示前i层楼，性别为u者距离0层的距离之和  
ll dp[maxn][2];//dp[i][u]表示第i层为u属性，第i+1层为另一属性，前i层不同性别到达自己的最近属性的寝室的最近距离和  
  
ll goup(int l,int r,int sex){   //表示[l+1,r]区间sex性别要去r+1的总距离  
    return (sum[r][sex]-sum[l][sex])*(r+1)-(dsum[r][sex]-dsum[l][sex]);  
}  
  
ll godown(int l,int r,int sex){  //表示[l+1,r]区间sex性别要去l的总距离  
    return dsum[r][sex]-dsum[l][sex]-(sum[r][sex]-sum[l][sex])*l;  
}  
  
ll cnt(int l,int r,int sex){   //在[l,r]都是sex属性，且l-1与r+1都为非sex属性的条件下。 [l,r]这些楼层非sex属性的人，去自己属性寝室的最小距离。  
    int mid=(l+r)>>1;  
    return godown(l-1,mid,sex)+goup(mid,r,sex);  
}  
int main()  
{  
    int n,m,i,j,T,cas=0;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d",&n);  
        sum[0][0]=sum[0][1]=0;  
        dsum[0][0]=dsum[0][1]=0;  
        for(i=1;i<=n;i++){  
            scanf("%lld%lld",&a[i],&b[i]);  
            sum[i][0]=sum[i-1][0]+a[i];  
            sum[i][1]=sum[i-1][1]+b[i];  
            dsum[i][0]=dsum[i-1][0]+a[i]*i;  
            dsum[i][1]=dsum[i-1][1]+b[i]*i;  
        }  
        memset(dp,0,sizeof(dp));  
        ll ans=1e18;  
        for(i=1;i<n;i++){  
            dp[i][0]=goup(0,i,1);  //这里先假设前i层都是性别0，i+1层是性别1所要的总距离  
            dp[i][1]=goup(0,i,0);  
            for(j=1;j<i;j++){  
                dp[i][0]=min(dp[i][0],dp[j][1]+cnt(j+1,i,1)   ); //依次使得前j层是1，使得第j,i+1都是1，这样就好状态转移了  
                dp[i][1]=min(dp[i][1],dp[j][0]+cnt(j+1,i,0)   );  
            }  
            ans=min(ans,dp[i][0]+godown(i,n,0)  ); //这里每一层都要更新一下ans，而不能最后才更新，因为最后才更新的话就不能使得后面几层都相同了  
            ans=min(ans,dp[i][1]+godown(i,n,1)  );  
        }  
        cas++;  
        printf("Case #%d: %lld\n",cas,ans);  
    }  
    return 0;  
}

<span>HDU5550 Game Rooms（dp）</span>

全站热榜