「BZOJ3437」小P的牧场

2014年11月29日6,2012

Description

背景

小P是个特么喜欢玩MC的孩纸。。。

描述

小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需要一定的花费（毕竟在控制站到牧场间修建道路是需要资源的嘛~），而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第i个牧场建立控制站的花费是ai，每个牧场i的放养量是bi，理所当然，小P需要总花费最小，但是小P的智商有点不够用了，所以这个最小总花费就由你来算出啦。

Input

第一行一个整数 n 表示牧场数目

第二行包括n个整数，第i个整数表示ai

第三行包括n个整数，第i个整数表示bi

Output

只有一行，包括一个整数，表示最小花费

Sample Input

4
2424
3142

Sample Output

9
样例解释
选取牧场1，3，4建立控制站，最小费用为2+(2+1*1)+4=9。
数据范围与约定
对于100%的数据，1<=n<=1000000,0<ai,bi<=10000

题解

这题正推比较烦。。。

反过来的话就so easy啦

假设只在n+1建站的话，费用sigma b[i]*(n-i)

f[i]表示考虑在i-n建站，且i有建的最大节省代价

f[i]=max{f[j]+sum[i]*(j-i)}-a[i] (sum[i]是b[i]的前缀和)

n^2的算法。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 9000000000000000000
#define MAX 1000000000000000000LL
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[1000005],b[1000005];
ll tot,ans,f[1000005],sum[1000005];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
	for(int i=1;i<n;i++)
		tot+=b[i]*(n-i);
	tot+=a[n];
	for(int i=n-1;i;i--)
	{
		for(int j=i+1;j<=n;j++)
			f[i]=max(f[i],f[j]+sum[i]*(j-i)-a[i]);
		ans=max(ans,f[i]);
	}
	printf("%lld",tot-ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define ll long long

#define inf 9000000000000000000

#define MAX 1000000000000000000LL

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[1000005],b[1000005];

ll tot,ans,f[1000005],sum[1000005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)b[i]=read();

for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];

for(int i=1;i<n;i++)

tot+=b[i]*(n-i);

tot+=a[n];

for(int i=n-1;i;i--)

{

for(int j=i+1;j<=n;j++)

f[i]=max(f[i],f[j]+sum[i]*(j-i)-a[i]);

ans=max(ans,f[i]);

}

printf("%lld",tot-ans);

return 0;

}

唔然后斜率优化一下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 9000000000000000000
#define MAX 1000000000000000000LL
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int l=1,r;
ll a[1000005],b[1000005];
int q[1000005];
ll tot,ans,f[1000005],sum[1000005];
double cal(int j,int k)
{
    return (double)(f[k]-f[j])/(double)(j-k);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
    for(int i=1;i<n;i++)
        tot+=b[i]*(n-i);
    tot+=a[n];
    q[++r]=n;
    for(int i=n-1;i;i--)
    {
        while(l<r&&cal(q[l],q[l+1])>sum[i])l++;
        int j=q[l];
        f[i]=f[j]+sum[i]*(j-i)-a[i];
        ans=max(ans,f[i]);
        while(l<r&&cal(q[r],i)>cal(q[r-1],q[r]))r--;
        q[++r]=i;
    }
    printf("%lld",tot-ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define ll long long

#define inf 9000000000000000000

#define MAX 1000000000000000000LL

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int l=1,r;

ll a[1000005],b[1000005];

int q[1000005];

ll tot,ans,f[1000005],sum[1000005];

double cal(int j,int k)

{

return (double)(f[k]-f[j])/(double)(j-k);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)b[i]=read();

for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];

for(int i=1;i<n;i++)

tot+=b[i]*(n-i);

tot+=a[n];

q[++r]=n;

for(int i=n-1;i;i--)

{

while(l<r&&cal(q[l],q[l+1])>sum[i])l++;

int j=q[l];

f[i]=f[j]+sum[i]*(j-i)-a[i];

ans=max(ans,f[i]);

while(l<r&&cal(q[r],i)>cal(q[r-1],q[r]))r--;

q[++r]=i;

}

printf("%lld",tot-ans);

return 0;

}

« 「BZOJ1010」[HNOI2008] 玩具装箱toy NOI2009诗人小G »

小蒟蒻

黄学长，请问样例的第二、三行为什么只有一个整数？

hzwer

空格没了

hzwer.com _ Home | http://hzwer.com

「BZOJ3437」小P的牧场

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论