差一个点,求帮助

P1064 [NOIP2006 提高组] 金明的预算方案

yzong @ 2017-07-06 10:42:05

第四个点过不去了

#include<iostream>
#include<stdio.h>
using namespace std;
int top,top2,m,n,v[61],p[61],q[61],cun1[1001],cun2[201],s[61][32001],ans[61],top3;
int max(int a,int b)
{
    if(a>b)
    return a;
    else
    return b;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d%d",&v[i],&p[i],&q[i]);
    for(int i=1;i<=n;i++)
    {
        if(q[i]==0)
        {
            top++;
            cun1[top]=v[i];
            cun2[top]=v[i]*p[i];
            for(int j=1;j<=n;j++)
            {
                if(q[j]==i)
                {
                    int jl=top;
                    for(int k=top2+1;k<=jl;k++)
                    {
                        top++;
                        cun1[top]=cun1[k]+v[j];
                        cun2[top]=cun2[k]+v[j]*p[j];
                    }
                }
            }
            top3++;
            ans[top3]=top-top2;
            top2=top;
        }
    }
    top2=0;
    for(int i=1;i<=top3;i++)
    {
        for(int j=1;j<=ans[i];j++)
        {
            top2++;
            for(int k=0;k<=m;k++)
            {
                if(k>=cun1[top2])
                s[i][k]=max(max(s[i-1][k],s[i][k]),s[i-1][k-cun1[top2]]+cun2[top2]);
            }
        }
    }
    printf("%d",s[top3][m]);
    return 0;
}

|