题目链接：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4007很好的一道题目，用f[i,j]表示前i个学生分为j个班时的最小unhappy值，状态转移方程为：f[i,j]=min{f[k,j-1],+(sum[i]-sum[k])*g[j]}.其中a<=i-k<=b,sum[i] = sigma {(x[s] -L)^2 | s≤ i}.
但现在的时间复杂度为O(k*n^2)，显然会TLE。将转移方程整理一下：f[i,j]=sum[i]*g[j]+min{f[k,j-1]-sum[k]*g[j]}. 显然可维护一个单调递增队列，每次转移之前将新的可选状态从队列尾插入，同时保证队列头的元素在可选范围之内。这样每次转移就可以只取队列头的元素，总的时间复杂度为O(n*k).
#include<iostream>
using namespace std;
const long long inf=100000000000000ll;
long long sum[10005],aver;
long long f[10005][205];
int x[10005],g[205];
int n,m,a,b;
typedef struct
{
long long unhap;
int loc;
}node;
node q[10005];
int main()
{
int test=0;
while(scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF)
{
test++;
aver=0;
int i,j;
for(i=1;i<=n;i++)
{
scanf("%d",&x[i]);
aver+=x[i];
}
aver/=n;
for(i=1;i<=m;i++)
scanf("%d",&g[i]);
sum[0]=0;
for(i=1;i<=n;i++)
sum[i]=sum[i-1]+(x[i]-aver)*(x[i]-aver);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
f[i][j]=inf;
f[0][0]=0;
long long ans_unhap=inf;
int ans_k=m+1,ans_t=n+1;
for(j=1;j<=m;j++)
{
int head=0,tail=0;
for(i=a;i<=n;i++)
{
node temp;
if(f[i-a][j-1]!=inf)
{
temp.unhap=f[i-a][j-1]-sum[i-a]*g[j];
temp.loc=i-a;
while(head<tail&&q[tail-1].unhap>=temp.unhap) tail--; //用>=是为了保证最后一个班的学生在多解的情况下人数最少。
q[tail].unhap=temp.unhap;
q[tail++].loc=temp.loc;
}
while(head<tail&&q[head].loc<i-b) head++;
if(head<tail) f[i][j]=q[head].unhap+sum[i]*g[j];
}
if(f[n][j]!=inf) //求多解情况下的最小分班数。
{
if(ans_unhap>f[n][j])
{
ans_unhap=f[n][j];
ans_k=j;
ans_t=n-q[head].loc;
}
}
}
if(test!=1) printf("\n");
if(ans_unhap==inf) printf("No solution.\n");
else printf("%lld %d %d",ans_unhap,ans_k,ans_t);
}
return 0;
}
posted on 2010-09-04 22:40
wuxu 阅读(360)
评论(0) 编辑 收藏 引用 所属分类:
动态规划