题意
有 \(n\) 件商品，第 \(i\) 件商品有基准价格 \(c_i\) 和抬价价格 \(p_i\)，\(p_i\) 互不相同，每件商品只能买一件，你有 \(S\) 元钱。
若你买了 \(k\) 件商品，则第 \(i\) 件商品的价格为 \(c_i+k\times p_i\)。问你最多能买多少件商品。
\(1\le c_i\le 10^9,0\le p_i,S\le 10^9,n\le 10^5\)。
思路
究极无敌诈骗题。
由于 \(p_i\) 互不相同，且每件商品最多只能买一次。则买 \(k\) 件商品的最低价格 \(s\) 即为 \(\sum_{i=1}^k 1+(i-1)*(k-i)\)。
简单二分得到 \(k=1918\) 时 \(s\le 10^9\)，\(k=1919\) 时 \(s>10^9\)，因此最优情况最多也只能买 \(1918\) 件商品。
假如你固定了要买的商品，显然有 \(p_i\) 从大到小购买价格最低。于是先将商品按照 \(p_i\) 从大到小排序。
设 \(f_{i,j}\) 表示购买第 \(1\sim i\) 件物品，且总共买了 \(j\) 件物品的价格最小值，则有 \(f_{i,j}=\min(f_{i-1,j},f_{i-1,j-1}+c_i+(j-1)\times p_i)\)。转移是朴素的，可以使用滚动数组优化。最后的答案即为满足 \(f_{n,ans}\le S\) 的 \(ans\) 最大值。
时间复杂度 \(O(n\times max_k)\)，可以通过。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mx=1900;
struct node{int c,p;
}a[100005];
bool cmp(node x,node y){return x.p==y.p?x.c<y.c:x.p>y.p;
}
int n,S,p,f[2][1905];
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n>>S;for(int i=1;i<=n;i++)cin>>a[i].c;for(int i=1;i<=n;i++)cin>>a[i].p;sort(a+1,a+1+n,cmp);memset(f,0x3f,sizeof(f));f[p][0]=f[p^1][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=mx;j++)f[p][j]=min(f[p][j],f[p^1][j-1]+a[i].c+(j-1)*a[i].p);for(int j=0;j<=mx;j++)f[p^1][j]=f[p][j];p^=1;}for(int i=mx;i>=0;i--){if(f[p][i]<=S){cout<<i;return 0;}}return 0;
}
)
)
