题目链接
题目大意
每层楼a个人喜欢打羽毛球，b个人喜欢游泳，但是现在一层楼只能有一个运动场馆，要你安排每一层建什么场馆，是的所有人到自己喜欢的运动场地的距离最小
思路
一层楼只能建羽毛球或者游泳馆，那么很容易想到DP的思路，一个$O(n^2)$的DP,
先定义状态
dp[i][0]表示第i层建羽毛球馆时，前i层所有人的最小距离
dp[i][1]表示第i层建游泳馆时，前i层所有人的最小距离
状态方程如下
其实就是假设第i层建羽毛球馆，第j+1~i-1层建游泳馆，第j层建羽毛球馆的贡献，那么第j+1~i-1层喜欢羽毛球的人则必须要i和j去，这样反复更新就可以了，sum函数求的是(j+1~,i)这个区间的人去往两边场馆的距离，这部分要求出来也有一定难度。
举个例子
1 2 3 4 5
我们维护两个数组，一个前缀和sum，一个i*a[i]的前缀和sum2
sum[i] = sum[i-1] + a[i]
sum2[i] = sum2[i-1] + a[i]*i
怎么求(2,3,4)去1，5的值呢？
对应一下
2 ~ 1 sum[2] = 1 + 2, sum2[2] = 11 + 22
3 ~ 2 sum[3] = 1+2+3, sum2[3] = 11+22+33
4 ~ 1 sum[4] = 1+2+3+4, sum2[4] = 11+22+33
前半部分
后半部分则减去(r+1)然后取绝对值即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 4e3+10;
ll dp[N][2];
ll pe[N],te[N];
ll sum[N][2],sum2[N][2];
int n;
ll calleft(int l,int r,int id){
ll x = sum[r][id] - sum[l-1][id];
ll y = sum2[r][id] - sum2[l-1][id];
return abs(y-x*(l-1));
}
ll calright(int l,int r,int id){
ll x = sum[r][id] - sum[l-1][id];
ll y = sum2[r][id] - sum2[l-1][id];
return abs(y-x*(r+1));
}
ll getans(int l,int r,int id){
if(l==1){
return calright(l,r,id);
}else if(r==n){
return calleft(l,r,id);
}else{
int mid = (l+r)>>1;
return calleft(l,mid,id) + calright(mid+1,r,id);
}
}
void solve(int cas){
scanf("%d",&n);
memset(sum,0,sizeof(sum));
memset(sum2,0,sizeof(sum2));
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%lld%lld",&te[i],&pe[i]);
sum[i][0] = sum[i-1][0] + te[i];
sum[i][1] = sum[i-1][1] + pe[i];
sum2[i][0] = sum2[i-1][0] + te[i]*i;
sum2[i][1] = sum2[i-1][1] + pe[i]*i;
}
for(int i=1;i<n;i++){
dp[i][0] = getans(1,i,0);
dp[i][1] = getans(1,i,1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
dp[i][0] = min(dp[j][1]+getans(j+1,i,0),dp[i][0]);
dp[i][1] = min(dp[j][0]+getans(j+1,i,1),dp[i][1]);
}
}
ll ans = min(dp[n][0],dp[n][1]);
printf("Case #%d: %lld\n",cas,ans);
}
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++){
solve(i);
}
}