Home > OI > poj 1513

poj 1513


本来拿这题熟悉Linux环境,结果迎来一坨WA+TLE,郁闷之极
设F(i,j)表示前i堂课讲前j个主题的最小不满意度,则
F(i,j)=Min{F(i-1,k)+cost[k+1,j]}
预处理cost的值
另外由于这题数据组数比较多,不要用memset初始化,否则超时严重

#include<stdio.h>
#include<string.h>
#define oo 0x77777777
#define MAXN 1010
int vis[MAXN][MAXN],f[MAXN][MAXN],n,L,C,sum[MAXN],Cost[MAXN][MAXN],viscost[MAXN][MAXN];
inline int min(int a, int b){
    return a<b?a:b;
}
int cost(int j, int i){
    if(viscost[j][i])
        return Cost[j][i];
    viscost[j][i]=1;
    if(j>i)
        return Cost[j][i]=0;
    int t=sum[i]sum[j1];
    t=Lt;
    if(t<=0) return Cost[j][i]=0;
    else if(1<=t&&t<=10)
        return Cost[j][i]=-C;
    else
        return Cost[j][i]=(t10)*(t10);
}
void dp(int i, int j){
    vis[i][j]=1;
    if(i==1){
        if(sum[j]<=L)
            f[i][j]=cost(1,j);
        return;
    }
    for(int k=j+1;k>=2;k){
        if(sum[j]sum[k1]>L) break;
        if(!vis[i1][k1])  dp(i1,k1);
        if(f[i1][k1]<oo)
            f[i][j]=min(f[i][j],f[i1][k1]+cost(k,j));
    }
}
int main(){
    int counter=0,n,x;
    while(scanf("%d",&n)!=EOF){
        int c=1;
        if(!n) break;
        ++counter;
        scanf("%d%d",&L,&C);
        for(int i=0;i<=n+1;++i) for(int j=0;j<=n+1;++j) f[i][j]=oo,vis[i][j]=Cost[i][j]=viscost[i][j]=0;
        for(int i=1,tmp=0;i<=n;++i){
            scanf("%d",&x);
            sum[i]=sum[i1]+x;
            tmp+=x;
            if(tmp>L){tmp=x;++c;}
        }
        dp(c,n);
        printf("Case %d:\n\n",counter);
        printf("Minimum number of lectures: %d\n",c);
        printf("Total dissatisfaction index: %d\n\n",f[c][n]);
    }
    return 0;
}
Categories: OI Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: