這是一道動態規劃的題目，狀態用
d[i][j][k][l]，表示取到第 i 個成品后手中還有 j 個A，k 個B，l 個C。
d[i+j][A][k+B][l+C]=min( d[i+j][A][k+B][l+C]，d[i][j][k][l]+1 )；
這是很容易想到的。
以下是我的程序：
#include<stdio.h>
#define maxint 30000
#define min(a,b) (a<b?a:b)
int n,d[101][11][11][11];
char a[101]=
{0};
void count(int begin,int end,int *A,int *B,int *C)
{//------begin -> end
int i;
(*A)=(*B)=(*C)=0;
for(i=begin;i<=end;i++)
{
if(a[i]=='A') (*A)++;
else if(a[i]=='B') (*B)++;
else if(a[i]=='C') (*C)++;
}
}
int main()
{
int i,j,k,l,A,B,C,m,ans;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("\n%c",&a[i]);
//------Read In
for(i=1;i<=n;i++)
for(j=0;j<=10;j++)
for(k=0;k<=10;k++)
for(l=0;l<=10;l++)
d[i][j][k][l]=-1;
count(1,(n>=10?10:n),&A,&B,&C);
d[(n>=10?10:n)][A][B][C]=0;
for(i=10;i<=n-1;i++)
for(j=0;j<=10;j++)
for(k=0;k<=10;k++)
for(l=0;l<=10;l++)
if(d[i][j][k][l]!=-1)
{
if(j!=0)
{
m=i+j;
if(m>n) m=n;
count(i+1,m,&A,&B,&C);
if(d[m][A][k+B][l+C]==-1) d[m][A][k+B][l+C]=maxint;
d[m][A][k+B][l+C]=min(d[m][A][k+B][l+C],d[i][j][k][l]+1);
}
if(k!=0)
{
m=i+k;
if(m>n) m=n;
count(i+1,m,&A,&B,&C);
if(d[m][j+A][B][l+C]==-1) d[m][j+A][B][l+C]=maxint;
d[m][j+A][B][l+C]=min(d[m][j+A][B][l+C],d[i][j][k][l]+1);
}
if(l!=0)
{
m=i+l;
if(m>n) m=n;
count(i+1,m,&A,&B,&C);
if(d[m][j+A][k+B][C]==-1) d[m][j+A][k+B][C]=maxint;
d[m][j+A][k+B][C]=min(d[m][j+A][k+B][C],d[i][j][k][l]+1);
}
}
ans=maxint;
for(i=0;i<=10;i++)
for(j=0;j<=10;j++)
for(k=0;k<=10;k++)
if(d[n][i][j][k]!=-1)
{
if(i>0) d[n][i][j][k]++;
if(j>0) d[n][i][j][k]++;
if(k>0) d[n][i][j][k]++;
ans=min(ans,d[n][i][j][k]);
}
printf("%d\n",ans);//------Print
return 0;
}
posted on 2010-01-06 18:48
lee1r 閱讀(369)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃