60,为什么?

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

Ouaoan @ 2016-06-30 17:30:39

#include<stdio.h>
#include<iostream>
using namespace std;
int m,n,s=0;
int w[61]= {0},c[61]= {0};
int a[61][4]= {0},b[61]= {0};
int f[32002]= {0};
int ji[3]= {0};
int main() {
    int i,j,k;
    cin>>m>>n;
    for(i=1; i<=n; i++) {    //输入,变形
        int q;
        cin>>w[i]>>c[i]>>q;
        c[i]*=w[i];
        if(q==0) {
            s++;
            b[s]=i;
        } else {
            a[q][0]++;
            a[q][a[q][0]]=i;
        }
    }
    cout<<"\n-----------\n\n";
    for(i=1; i<=n; i++) {
        cout<<w[i]<<' '<<c[i]<<endl;
    }
    cout<<"\n-----------\n\n";
    for(i=1; i<=s; i++) {
        cout<<b[i]<<' ';
        for(j=1; j<=a[i][0]; j++) {
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    cout<<"\n-----------\n\n";
    getchar();
    for(i=1; i<=s; i++) {
        for(j=m; j>=10; j-=10) {
            int tmp1=a[i][1],tmp2=a[i][2];
            if(j>=w[b[i]])
                f[j]=max(f[j],f[j-w[b[i]]]+c[b[i]]);
            if(j>=w[b[i]]+w[tmp1])
                f[j]=max(f[j],f[j-w[b[i]]-w[tmp1]]+c[tmp1]+c[b[i]]);
            if(j>=w[b[i]]+w[tmp2])
                f[j]=max(f[j],f[j-w[b[i]]-w[tmp2]]+c[tmp2]+c[b[i]]);
            if(j>=w[b[i]]+w[tmp1]+w[tmp2])
                f[j]=max(f[j],f[j-w[b[i]]-w[tmp1]-w[tmp2]]+c[tmp1]+c[tmp2]+c[b[i]]);
            printf("%5d",f[j]);
        }
        cout<<endl;
        getchar();
    }
    cout<<f[m];
    return 0;
}

/* 10 5 8 2 0 4 5 1 3 5 1 4 3 0 5 2 0

10 6 8 2 0 4 5 1 3 5 1 4 3 0 1 3 2 5 2 0

200 10 50 1 0 40 4 0 30 5 1 40 5 1 20 5 0 50 4 5 40 4 0 32 2 0 41 3 0 40 3 5

1000 5 500 4 2

400 4 0

320 2 0

410 3 0

400 3 2

*/


by joyemang33 @ 2016-06-30 22:56:00

数组可以开大一点


|