题目大意：有n首歌，m个光盘，每个光盘最多能放t时间的歌，给出每首歌的长度，必须按顺序录入光盘（可以选择不录某几首歌），最多能录多少首歌。

?

?

用d[i][j][0]表示前i首歌，放j首，最少用多少个光盘，用d[i][j][1]表示前i首歌，放j首，在光盘最少的前提下，最后一个光盘可以剩余的最多容量。根据是否放第i首歌完成递推。

这样递推是正确的，因为前i首歌，放j首的情况下，最佳的情况就是尽量少的用光盘，并且使得最后一个光盘容量尽量大（例如如果用的光盘数多一些，并且最后一个光盘的容量更大一些，这样的情况不如前面的好）。在程序中使用了滚动数组优化内存。

?

状态转移方程：

若d[i-1][j][1]>=a[i]，则若放i，光盘数不变，剩余容量变少，

若d[i-1][j][1]

?

?

#include
  
   
#include
   
     #include
    
      int a[1530]; int d[2][1530][2]; char e[100010]; int main(void) { int i,j,v,n,m,pi,qi,p1,p2,minp1,minp2,sump,top,lo,cur,ans; scanf("%d",&pi); for(qi=1;qi<=pi;qi++) { scanf("%d%d%d",&n,&v,&m); while(getchar()==' ') { ; } gets(e+1); lo=strlen(e+1); top=0; i=1; while(i<=lo) { if((e[i]>='0')&&(e[i]<='9')) { sump=0; while((e[i]>='0')&&(e[i]<='9')) { sump=sump*10+e[i]-'0'; i++; } top++; a[top]=sump; } else { i++; } } cur=1; for(i=1;i<=n;i++) { cur^=1; if(d[cur^1][i-1][1]>=a[i]) { d[cur][i][0]=d[cur^1][i-1][0]; d[cur][i][1]=d[cur^1][i-1][1]-a[i]; } else { d[cur][i][0]=d[cur^1][i-1][0]+1; d[cur][i][1]=v-a[i]; } for(j=1;j
     
      =a[i]) { p1=d[cur^1][j-1][0]; p2=d[cur^1][j-1][1]-a[i]; if((p1
      
       minp2))) { minp1=p1; minp2=p2; } } else { p1=d[cur^1][j-1][0]+1; p2=v-a[i]; if((p1
       
        minp2))) { minp1=p1; minp2=p2; } } d[cur][j][0]=minp1; d[cur][j][1]=minp2; } } ans=0; for(i=n;i>=1;i--) { if(d[cur][i][0]<=m) { ans=i; break; } } printf("%d\n",ans); if(qi!=pi) { printf("\n"); } } return 0; }
       
      
     
    
   
  

?