HDU5550 Game Rooms（dp）-白红宇

HDU5550 Game Rooms（dp）

阅读量：6246 次

发布时间：2019-06-22

本文共 1526 字，大约阅读时间需要 5 分钟。

题意：

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

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

思路：

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

#include
     
        #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
            #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  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

转载于:https://www.cnblogs.com/d-e-v-i-l/p/6110862.html

你可能感兴趣的文章