DP上课覆盖知识点，POJ(1513)

题目链接：http://poj.org/problem?id=1513

解题报告：

思路：

知识点从第二个开始扫，递推表达式是：minlec[i]=min(minlec[k])+1,并且要保证，time[k+1]+...+time[i]<L，即在一节课之内上完知识点k+1到知识点i;

要是minlec[i]==minlec[k]+1;就要比较他的不满意度了。

很有趣的一道题，不过还是WA了很多次，还有一点就是输出格式。

#include<cstdio>
#include<iostream>
using namespace std;

int C;

int DI(int t)
{
     if(t==0) return 0;
     else if(t>=1&&t<=10) return -C;
     else return (t-10)*(t-10);
}

int main()
{
   int n,L,count=0,i,j;
   int time[1010];      ///每个知识点要的时间
   int minLec[1010];    ///知识点1~i最少要上的课的节数
   int minDis[1010];    ///对应的不满意度

   while(scanf("%d",&n),n)
   {
       count++;
       if(count>1)
           printf("
");

       scanf("%d %d",&L,&C);

       for(i=1;i<=n;i++)
           scanf("%d",&time[i]);
       minLec[0]=minDis[0]=0;

       minLec[1]=1;
       minDis[1]=DI(L-time[1]);

       for(i=2;i<=n;i++)
       {
           minLec[i]=minLec[i-1]+1;
           minDis[i]=minDis[i-1]+DI(L-time[i]);

           int sum=time[i];
           for(j=i-1;j>0;j--)
           {
               sum+=time[j];
               if(sum<=L)
               {
                   int cost=minDis[j-1]+DI(L-sum);
                   if(minLec[i]>minLec[j-1]+1)
                   {
                       minLec[i]=minLec[j-1]+1;
                           minDis[i]=cost;
                   }
                   else if(minLec[i]==minLec[j-1]+1)
                       minDis[i]=minDis[i]>cost?cost:minDis[i];
               }
               else
                   break;
           }
       }
       printf("Case %d:

",count);
       printf("Minimum number of lectures: %d
",minLec[n]);
       printf("Total dissatisfaction index: %d
",minDis[n]);
   }
   return 0;
}