The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

除夕之夜的动态规划 POJ 1015 Jury Compromise

写了3个小时终于过了,这道题让我进一步了解和掌握了动态规划,呵呵:-)
#include<iostream>
#include
<cstdio>
#include
<algorithm>
using namespace std;
#define offset ((20*m))

int f[100][2000];
int path[100][2000];

int minu[400];
int plus[400];

int a[400];
int b[400];
int n,m;

#define max(a,b) ((a>b?a:b))
bool check(int i,int n,int m)
{
    
while(true)
    
{

        
if(i==path[n][m])
            
return true;
        
if(n==0)
            
break;
        m
-=minu[path[n][m]];
        n
-=1;
        
    }

    
return false;
}

int record[1000];


int main()
{
    
int i,j,k;
    
int testcase=0;
    
while(scanf("%d%d",&n,&m))
    
{
        testcase
++;
        memset(path,
-1,sizeof(path));
        memset(f,
-1,sizeof(f));
        
if(n==0&&m==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d%d",&a[i],&b[i]);
            minu[i]
=a[i]-b[i];
            plus[i]
=a[i]+b[i];
        }

        
for(i=1;i<=n;i++)
        
{
                
if(plus[i]>=f[1][minu[i]+offset])
                
{

                    f[
1][minu[i]+offset]=plus[i];
                    path[
1][minu[i]+offset]=i;
                }

        }


        
for(i=1;i<m;i++)
        
{
            
for(j=0;j<=offset*2;j++)
            
{
                
for(k=1;k<=n;k++)
                
{
                    
if(f[i][j]>=0)
                    
{
                        
if(!check(k,i,j))
                        
{
                            
if(f[i][j]+plus[k]>=f[i+1][j+minu[k]])
                                path[i
+1][j+minu[k]]=k;
                            f[i
+1][j+minu[k]]=max(f[i+1][j+minu[k]],f[i][j]+plus[k]);
                            
                        }

                    }




                }

            }

        }

        
        
int mark;
        
for(i=0;i<=20*m;i++)
        
{
            
if(  f[m][20*m+i]!=-1  ||  f[m][20*m-i]!=-1 )
            
{
                mark
=20*m+i;
                
if(f[m][20*m+i]>=f[m][20*m-i])
                
{
                    mark
=20*m+i;
                }

                
if(f[m][20*m+i]<f[m][20*m-i])
                
{
                    
                    mark
=20*m-i;
                }

                
break;
                
            }

        }

        
int t,tt;
        t
=m;
        tt
=mark;
        
for(i=1;i<=m;i++)
        
{
            record[i]
=path[t][tt];
            t
-=1;
            tt
-=minu[record[i]];
        }

        sort(record
+1,record+1+m);

        
int suma=0;
        
int sumb=0;
        
for(i=1;i<=m;i++)
        
{

            suma
+=a[record[i]];
            sumb
+=b[record[i]];
        }

        printf(
"Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",testcase,suma,sumb );
        
for(i=1;i<=m;i++)
            printf(
" %d",record[i]);
        printf(
"\n\n");
    }

    
return 0;
}

posted on 2010-02-13 19:03 abilitytao 阅读(1885) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理