专栏文章

AT_abc415_g 题解

MMoya_Rao啾？啾！
AT_abc415_g题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miotkpm6
此快照首次捕获于
2025/12/03 00:55
3 个月前
此快照最后确认于
2025/12/03 00:55
3 个月前
查看原文
也许更好的阅读体验？
G 的难度在下降！噢耶。
我记着 ABC413 也是个很水的 G 啊。居然存在同等级的！太棒惹。
首先读入，但要干掉一点的。比方说，Ai=AjA_i = A_j，但是 Bi>BjB_i > B_j，那高桥是不存在一点可能性去使用 jj 方案的。
也就是说实际上的 mm 不超过 300300。这样可以省去好多时间！
干完之后按照比例排序，找比例最大的，先一降到底。
然后跑完全背包即可。
注意这个完全背包的总容量是被比例最大的那个降过以后的 nn，然后价值是 BiB_i，代价是 Ai−BiA_i-B_i。
注意这里有一个特殊的性质就是容量必须 ≥Ai\ge A_i，虽然耗费的容量只有 Ai−BiA_i-B_i。毕竟转回题目其本质，是要先给出 AiA_i 再还回来 BiB_i 的。所以一开始没有 AiA_i 个的话你就没戏了。
注意一开始的“一降到底”不必要全降。也可能不降。
这里给一组精心创造的 Hack 数据：
CPP
97 3
60 30
40 19
56 27
如果我们一开始使用比例最大的，也就是 i=1i=1 的那一组，那么我们只能降一次，对吧，然后后面的两种就都用不了了；但反观后面两种，虽然比例都没第一种大，但是加起来很赚，比起直接消耗第一种，用这种方案最终喝到的可乐数反而更多。
那我们干脆开大点得了。由于时间复杂度支持 10510^5，那就给降到 10510^5 吧。
嗯然后就没有了。实现都比较简单，具体看代码吧。
CPP
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5+5;
struct node{LL x,y,d;}a[N];
LL n,m,Id,ans,dp[N];
int main(){
    cin>>n>>m;Id=1,ans=n;
    for(int i=1;i<=m;i++){LL x,y;cin>>x>>y;a[x].y=max(a[x].y,y);}
    for(int i=1;i<=300;i++)a[i].x=i,a[i].d=a[i].x-a[i].y;
    for(int i=2;i<=300;i++)if(a[i].y*a[Id].x>a[i].x*a[Id].y)Id=i;
    if(n>600){
        LL tmp=(n-600+a[Id].d)/a[Id].d;
        ans+=tmp*a[Id].y;n-=tmp*a[Id].d;
    }
    for(int i=1;i<=300;i++)for(int j=a[i].x;j<=n;j++)
        dp[j]=max(dp[j],dp[j-a[i].d]+a[i].y);
    ans+=dp[n];cout<<ans<<"\n";
    return 0;
}
upd：那玩意儿降到 9000090000，即 3002300^2，也是行得通的。各位如果有时间可以试着 Hack 一下 9000090000 以内的哦。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...