后 5个点tle,求助怎么优化

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

boolex @ 2022-05-19 13:04:24

//看的题解的思路,大概就是说,先把同属于一个组里的东西先进行01背包,然后得到从主件花费到n的这么一个数组,然后再把这个数组往总的dp数组里放

#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node
{
    int v;
    int w;
};
vector<node>h[65];
int dp[32005],f[32005], ff[32005];

int main()
{

    int v,p,q;
    node x;
    scanf("%d%d",&n,&m);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v,&p,&q);
        x.v=v;
        x.w=v*p;
        if(q==0) h[i].push_back(x);//主件就入自己的队
        else h[q].push_back(x);//附件就入主件的队
    }
    for(int i=1;i<=m;i++)
    {
        if(h[i].size()==0) continue;//如果不存在以i为主件的数组,continue
        int vv=h[i][0].v;//0号是主件,vv是主件的体积(本题中为价钱)
        int ww = h[i][0].w;//主件的重要性
        int num=h[i].size()-1;//附件的数量
        ///cout<<vv<<" "<<ww<<" "<<num<<endl;//应该是没问题
        //h[i][j]表示以i为主件的物品的所有附近,其中h[i][0]就是主件自己
        //我要先对每个附件组进行dp,然后得出从0到V-c[i]的所有对应的值,即f'[0..V-c[i]]
        //要先对除了主件以外的附件进行01背包,否则主件的体积会被算好几遍,然后最后都要加上主件的价值和重要度,

        memset(f, 0, sizeof(f));
        memset(ff, 0, sizeof(ff));
        for(int j = 1; j<=num; j++)//对所有的附件进行01背包
            for(int k = n-vv; k>=h[i][j].v;k--){
                f[k] = max(f[k], f[k-h[i][j].v]+h[i][j].w);
                ///cout<<f[k];

            }

        //加上主件的价格和价值
        for(int j = 0; j<=n-vv; j++){//ff[0]就是只买主件
            ff[j+vv] = f[j]+ww;//游标就是他的花费,函数值就是他的重要度
            ///cout<<ff[j+vv];
        }
        ///cout<<ff[1199]<<" ";应该也没问题

        //再放进到真正的背包里
        //小于vv的就相当于啥也没放
        //一共有从vv到n个物品
        for(int k = n; k>=vv; k--)//这里还是有分组背包的感觉,就是ff中的这些数是互相冲突的,只能放一个,所以外层for先写容量
            for(int j = vv; j<=n; j++)//依赖背包就是把附件主件这些,转化成了m-vv+1个物品(加的那个1就是只买主件的情况)
                if(k>=j)dp[k] = max(dp[k], dp[k-j]+ff[j]);

       //cout<<dp[n]<<endl;

    }
    printf("%d",dp[n]);
    return 0;
}

by 阿丑 @ 2022-05-19 16:47:41

@boolex

for(int k = n; k>=vv; k--)
    for(int j = vv; j<=n; j++)

这个循环中的语句可以认为执行了 n^2 次,所以复杂度是 \mathcal O(mn^2) 的,会 T。

事实上这题有特殊性:

他还从因特网上查到了每件物品的价格(都是 10 元的整数倍)。

可以借此优化。


by boolex @ 2022-05-19 17:02:45

已经解决了,即背包九讲中P02“一个简单有效的方法”,把价格不同,而重要性一样的物品只保留一件,核心代码如下

fffsize = 0;
        for(int j = vv-1; j<=n; j++)//细节vv-1,因为第一个数是肯定要的,所以vv-上一个1就可以把这个数也带进来。相当于一个没有附件的物品,也会被放进fff中
            if(ff[j+1]>ff[j])
                {
                    fffsize++;
                    fff[fffsize].v = j+1;
                    fff[fffsize].w = ff[j+1];
                }

完整AC代码


|