历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 6. 氧气与臭氧原题链接困难

作者：

lixiaoqian_qwq , 2020-07-01 12:27:24 , 所有人可见 , 阅读 1012

3

1

玄学O2O3,仅用200ms,以多重背包问题Ⅱ的方法碾压1000ms的单调队列优化！

这样实现的：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
using namespace std ;
const int N=1000010 ;
int a,b,s ;
int n,m ;
int cnt ;
int f[N] ;
int w[N],v[N] ;
int main()
{
    scanf("%d%d",&n,&m) ;
    while(n--)
    {
        scanf("%d%d%d",&a,&b,&s) ;
        for(int i=1;i<=s;i*=2)
        {
            v[++cnt]=a*i ;
            w[cnt]=b*i ;
            s-=i ;
        }
        if(s)
        {
            v[++cnt]=a*s ;
            w[cnt]=b*s ;
        }
    }
    n=cnt ;
    for(int i=1;i<=n;i++)   
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]) ;
    printf("%d",f[m]) ;
    return 0 ;
}

看代码前两行，发现了什么？

对，就是O2和O3!

7 评论

cht 2020-07-01 14:16

玄学的发现最后多重背包2也能用多重背包1+O2O3优化卡过去。

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m, v[N], w[N],s[N],f[N][N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    cout << f[n][m];
}

ACtg 2020-10-02 23:49

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")