20分悬关求助

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

chengjing @ 2024-05-09 23:03:47

//典型的背包问题01 
// 但是又附加条件及附件的购买
//前面选择会影响后面，要标记 
#include<stdio.h>
int a[100][8]={0};//自己，等级，子件数，子1，2 
int b[100][10005]={0};
int main()
{
    int i,j,k,n,m,q,w,e,l,max;
    scanf("%d%d",&n,&m);
    j=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q,&w,&e);
        if(e==0)
        {
            a[j][0]=q;
            a[j][1]=w;
            a[j][2]=e;
            j++;
        }
        else
        {
            a[e][2]++;
            a[e][2+a[e][2]*2-1]=q;
            a[e][2+a[e][2]*2]=w;
        }
    }
    k=j-1;
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=n;j++)
        {
            b[i][j]=b[i-1][j];
            if(b[i-1][j-a[i][0]]+a[i][1]*a[i][0]>b[i][j]&&j-a[i][0]>=0)
            {
                b[i][j]=b[i-1][j-a[i][0]]+a[i][1]*a[i][0];
            }
            if(b[i-1][j-a[i][0]-a[i][3]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]>b[i][j]&&j-a[i][0]-a[i][3]>=0&&a[i][2]>=1)
                b[i][j]=b[i-1][j-a[i][0]-a[i][3]]+a[i][1]*a[i][0]+a[i][4]*a[i][3];
            if(b[i-1][j-a[i][0]-a[i][5]]+a[i][1]*a[i][0]+a[i][6]*a[i][5]>b[i][j]&&j-a[i][0]-a[i][5]>=0&&a[i][2]==2)
                b[i][j]=b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][6]*a[i][5];
            if(b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]+a[i][6]*a[i][5]>b[i][j]&&j-a[i][0]-a[i][3]-a[i][5]>=0&&a[i][2]==2)
                b[i][j]=b[i-1][j-a[i][0]-a[i][3]-a[i][5]]+a[i][1]*a[i][0]+a[i][4]*a[i][3]+a[i][6]*a[i][5];
        }
    }
    for(i=1;i<=k;i++)
    {
        for(j=0;j<=6;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    for(i=1;i<=k;i++)
    {
        for(j=100;j<=n;j=j+100)
        {
            printf("%d ",b[i][j]);
        }
        printf("\n");
    }
    printf("%d",b[k][n]);
 }

by chengjing @ 2024-05-09 23:05:39

感觉代码没什么问题，但是第二组数组没过 2000 10 500 1 0 400 4 0 300 5 1 400 5 1 200 5 0 500 4 5 400 4 0 320 2 0 410 3 0 400 3 5 这个是数据我的答案是7200 自己模拟也是但是答案是7430

by lry0404 @ 2024-05-25 14:00:38

#include <iostream>
using namespace std;
int n, m, v[65], p[65], q[65], c1[65], c2[65], gv[65][4], gw[65][4], f[32005];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i])
            if (c1[q[i]])
                c2[q[i]] = i;
            else
                c1[q[i]] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        if(q[i] == 0)
        {
            for(int j = 0; j <= 1; j++)
            {
                for(int k = 0; k <= 1; k++)
                {
                    gv[i][j * 2 + k] = j * v[c1[i]] + k * v[c2[i]] + v[i];
                    gw[i][j * 2 + k] = j * v[c1[i]] * p[c1[i]] + k * v[c2[i]] * p[c2[i]] + v[i] * p[i];
                }
            }
        }
    }
    for(int i = 1; i <= m; i++)
    {
        if(q[i] == 0)
        {
            for(int j = n; j >= 0; j--)
            {
                for(int k = 0; k < 4; k++)
                {
                    if(j >= gv[i][k])
                    {
                        f[j] = max(f[j], f[j - gv[i][k]] + gw[i][k]);
                    }
                }
            }
        }
    }
    cout << f[n] << endl;
    return 0;
}

by lry0404 @ 2024-05-25 14:01:16

by lry0404 @ 2024-05-30 13:09:08

分组背包