方法一：
#include<iostream>
using namespace std;
int n,s;
int c[5001],t[5001];
int f[5001][5001];
int main()
{
freopen("batch.in","r",stdin);
freopen("batch.out","w",stdout);
scanf("%d%d",&n,&s);
c[0]=0; t[0]=0;
memset(f,0x7F,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;++i){
scanf("%d%d",&t[i],&c[i]);
t[i]+=t[i-1];
c[i]+=c[i-1];
f[1][i]=(t[i]+s)*c[i];
}
int MAX=f[1][n];
for(int k=2;k<=n;++k){
for(int i=k;i<=n;++i){
for(int ti=i;ti>=k;--ti)
if(f[k][i]>f[k-1][ti-1]+(c[i]-c[ti-1])*(s+t[i]+(s*(k-1)))){
f[k][i]=f[k-1][ti-1]+(c[i]-c[ti-1])*(s+t[i]+(s*(k-1)));
}
}
if(f[k][n]<MAX) MAX=f[k][n];
}
printf("%d\n",MAX);
return 0;
}
方法二：
#include<iostream>
using namespace std;
int n,s;
int t[5001],f[5001];
long long sum[5001];
int main()
{
freopen("batch.in","r",stdin);
freopen("batch.out","w",stdout);
scanf("%d%d",&n,&s);
t[0]=f[0]=0;
for(int i=1;i<=n;++i){
scanf("%d%d",&t[i],&f[i]);
t[i]+=t[i-1];
f[i]+=f[i-1];
}
sum[0]=0;
for(int i=1;i<=n;++i){
sum[i]=0x7FFFFFFF;
for(int j=i-1;j>=0;--j)
if(sum[i]>sum[j]+(t[i]+s)*(f[i]-f[j])+s*(f[n]-f[i]))
sum[i]=sum[j]+(t[i]+s)*(f[i]-f[j])+s*(f[n]-f[i]);
}
printf("%lld\n",sum[n]);
return 0;
}
方法三：
posted on 2009-04-13 12:18
xfstart07 阅读(91)
评论(0) 编辑 收藏 引用 所属分类:
代码库