POJ 1015 公正陪审团问题 动态规划

这题想了很久，是经典的动态规划问题，感觉有点难度，在网上看了很多讨论。

看了动态规划还要好好加强。

#include <iostream>
using namespace std;
int main()
{
    long i,j,k,l,n,m,t1,maxf,count;
    long p[210],d[210],f[210],s[210];
    long can[30];
    long res[30][1000],from[30][1000];
    
    count=0;
    cin>>n>>m;
    while(n!=0 || m!=0)
    {
        count++;
        
        for(i=0;i<n;i++)
        {
            cin>>p[i]>>d[i];
            f[i]=p[i]-d[i];
            s[i]=p[i]+d[i];
        }
        maxf=20*m;
        
        for(i=0;i<=m;i++)
			for(j=0;j<=maxf*2;j++)
				res[i][j]=-1;
			res[0][maxf]=0;
			from[0][maxf]=-1;
			
			for(i=0;i<m;i++)
				for(j=0;j<=maxf*2;j++)
					if(res[i][j]!=-1)
					{
						for(k=0;k<n;k++)
						{
							t1=j;
							for(l=i;l>0;l--)
							{
								if(from[l][t1]==k) break;
								t1-=f[from[l][t1]];
							}
							if(l!=0) continue;
							
							t1=res[i][j]+s[k];
							if(res[i+1][j+f[k]]<t1)
							{
								res[i+1][j+f[k]]=t1;
								from[i+1][j+f[k]]=k;
							}
						}
					}
					
					for(i=0;i<=maxf;i++)
					{
						if(res[m][maxf+i]>res[m][maxf-i]) { t1=maxf+i; break;}
						if(res[m][maxf-i]!=-1) { t1=maxf-i; break;}
					}
					
					cout<<"Jury #"<<count<<endl;
					cout<<"Best jury has value "<<(res[m][t1]+t1-maxf)/2<<" for prosecution";
					cout<<" and value "<<(res[m][t1]-t1+maxf)/2<<" for defence:"<<endl;
					
					for(i=m;i>0;i--)
					{
						can[i]=from[i][t1];
						t1-=f[can[i]];
					}
					
					for(i=1;i<m;i++)
						for(j=i+1;j<=m;j++)
							if(can[i]>can[j]) swap(can[i],can[j]);
							
							for(i=1;i<=m;i++)
								cout<<" "<<can[i]+1;
							cout<<endl<<endl;
							
							cin>>n>>m;
    }
    return 0;
}