求大佬解决RE

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

童煜智 @ 2018-03-11 12:43:41

include<bits/stdc++.h>

using namespace std; struct jm { int v,p,q,x; }a[100]; int j; int m,n,f[10000];//这儿！！！ int b[5]; int mmax(int k) { int t=0; for(int i=1;i<=n;i++) if(a[i].q==a[k].x) b[++t]=i; if(t==0) return max(f[j-a[k].v]+a[k].va[k].p,f[j]); else if(t==1) { if(f[j-a[k].v]+a[k].va[k].p>f[j]) return max(f[j-a[k].v]+a[k].va[k].p,f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p); else return f[j]; } else if(t==2) { if(f[j-a[k].v]+a[k].va[k].p>f[j]) { int ans=0; if(ans<f[j-a[k].v]+a[k].va[k].p) ans=f[j-a[k].v]+a[k].va[k].p; if(ans<f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p) ans=f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p; if(ans<f[j-a[k].v-a[b[2]].v]+a[k].va[k].p+a[b[2]].va[b[2]].p) ans=f[j-a[k].v-a[b[2]].v]+a[k].va[k].p+a[b[2]].va[b[2]].p; if(ans<f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p+a[b[2]].va[b[2]].p) ans=f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p+a[b[2]].va[b[2]].p; return ans; } else return f[j];
} } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q); a[i].x=i; } for(int i=1;i<=m;i++) if(a[i].q==0) for(j=n;j>=a[i].v;j--) f[j]=mmax(i);
printf("%d",f[n]); return 0; }

//f数组的大小会影响答案，why？开小了答案对但RE，开大了答案错

by 单曦增 @ 2018-03-11 13:43:25

@童煜智程序编译不通过啊

by 童煜智 @ 2018-03-13 16:09:10

include<bits/stdc++.h>

using namespace std; struct jm { int v,p,q,x; }a[100]; int j; int m,n,f[32010]; int b[5]; int mmax(int k) { int t=0; for(int i=1;i<=n;i++) if(a[i].q==a[k].x) b[++t]=i; if(t==0) return max(f[j-a[k].v]+a[k].va[k].p,f[j]); else if(t==1) { if(f[j-a[k].v]+a[k].va[k].p>f[j]) return max(f[j-a[k].v]+a[k].va[k].p,f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p); else return f[j]; } else if(t==2) { if(f[j-a[k].v]+a[k].va[k].p>f[j]) { int ans=0; if(ans<f[j-a[k].v]+a[k].va[k].p) ans=f[j-a[k].v]+a[k].va[k].p; if(ans<f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p) ans=f[j-a[k].v-a[b[1]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p; if(ans<f[j-a[k].v-a[b[2]].v]+a[k].va[k].p+a[b[2]].va[b[2]].p) ans=f[j-a[k].v-a[b[2]].v]+a[k].va[k].p+a[b[2]].va[b[2]].p; if(ans<f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p+a[b[2]].va[b[2]].p) ans=f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].va[k].p+a[b[1]].va[b[1]].p+a[b[2]].va[b[2]].p; return ans; } else return f[j];
} } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q); a[i].x=i; } for(int i=1;i<=m;i++) if(a[i].q==0) for(j=n;j>=a[i].v;j--) f[j]=mmax(i);
printf("%d",f[n]); return 0; }

by 童煜智 @ 2018-03-13 16:12:37

include<bits/stdc++.h>

using namespace std;

struct jm

{

int v,p,q,x;

}a[100];

int j; int m,n,f[32010];

int b[5];

int mmax(int k)

{

int t=0; 

for(int i=1;i<=n;i++)

  if(a[i].q==a[k].x)

    b[++t]=i;

if(t==0) return max(f[j-a[k].v]+a[k].v*a[k].p,f[j]);

else if(t==1)

{
    if(f[j-a[k].v]+a[k].v*a[k].p>f[j]) 
      return max(f[j-a[k].v]+a[k].v*a[k].p,f[j-a[k].v-a[b[1]].v]+a[k].v*a[k].p+a[b[1]].v*a[b[1]].p);
    else return f[j];
}
else if(t==2)
{
    if(f[j-a[k].v]+a[k].v*a[k].p>f[j])
    {
        int ans=0;
        if(ans<f[j-a[k].v]+a[k].v*a[k].p) 
          ans=f[j-a[k].v]+a[k].v*a[k].p;
        if(ans<f[j-a[k].v-a[b[1]].v]+a[k].v*a[k].p+a[b[1]].v*a[b[1]].p)
          ans=f[j-a[k].v-a[b[1]].v]+a[k].v*a[k].p+a[b[1]].v*a[b[1]].p;
        if(ans<f[j-a[k].v-a[b[2]].v]+a[k].v*a[k].p+a[b[2]].v*a[b[2]].p)
          ans=f[j-a[k].v-a[b[2]].v]+a[k].v*a[k].p+a[b[2]].v*a[b[2]].p;
        if(ans<f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].v*a[k].p+a[b[1]].v*a[b[1]].p+a[b[2]].v*a[b[2]].p)
          ans=f[j-a[k].v-a[b[1]].v-a[b[2]].v]+a[k].v*a[k].p+a[b[1]].v*a[b[1]].p+a[b[2]].v*a[b[2]].p;
        return ans;
    }
    else return f[j];      
}

}

int main()

{

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
    scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
    a[i].x=i;
}
for(int i=1;i<=m;i++)
  if(a[i].q==0)
    for(j=n;j>=a[i].v;j--)
      f[j]=mmax(i);   
printf("%d",f[n]);
return 0;

}