- D - Pearls https://vjudge.net/problem/HDU-1300
- HDU - 1300
这个题目也是一个比较裸的斜率 dp, 依照之前可以推一下这个公式, 这个很好推
这个注意题目已经按照价格升序排列序, 所以还是前缀和还是单调的.
sum[i] 表示前面 i 种珍珠的花费的前缀和
dp[i] 表示买前面 i 种珍珠需要的最少的花费
dp[i]=min(dp[j]+(sum[i]-sum[j]+10)*c[i]
j>k 如果要求选 j 更优, 则需要满足下列式子
dp[j]+(sum[i]-sum[j]+10)*c[i]<dp[k]+(sum[i]-sum[j]+10)*c[i]
上面式子化简可得
dp[j]-dp[k]<c[i]*(sum[j]-sum[k])
令 G[j,k]=(dp[j]-dp[k])/(sum[j]-sum[k])
如果 G[j,k]<c[i] 且 j>k 则选 j 比选 k 更优
推出这个斜率的式子之后, 然后要用它.
关键的来了: 现在从左到右, 还是设 k<j<i, 如果 g[i,j]<g[j,k], 那么 j 点便永远不可能成为最优解, 可以直接将它踢出我们的最优解集. 为什么呢?
分三种情况讨论
1 G[i,j]<G[j,k]<c[t] 那么 i 是比 j 更优的 所以可以排除 j 点
2 G[i,j]<c[t]<G[j,k] 那么 i 也是比 j 更优的, 而且 k 比 j 也优 可以排除 j 点
3 c[t]<G[i,j]<G[j,k] 那么 k 是比 j 更优 可以排除 j 点
所以如果是 G[i,j]<G[j,k] 且 i>j>k 那么就可以排除掉 j 这个情况, 因为 j 两边永远可以找到一个比它更优的, 这个也是一种优化
那如果 G[i,j]>G[j,k] i>j>k 这种情况呢?
1 G[i,j]>G[j,k]>c[t] 那么 j 比 i 更优 k 比 j 更优
2 G[i,j]>c[t]>G[j,k] 那么 j 比 i 更优 j 也比 k 更优
3 c[t]>G[i,j]>G[j,k] 那么 i 比 j 更优 j 比 k 更优
这个就可以找到单调性了,
如果 i 从小往大 G[i,j] 越来越大, 那么在 小于等于 c[t] 的范围内, 情况也更优,
意思是 如果 i>j>k 如果可以在 j 点取得最优解, 那么 k 点肯定可以排除,
所以就是找小于 c[t] 的最大的这个 j .
如果是 G[i,j]<Gj,k]&&i>j>k 这种情况可以找到一个 j 比两端都优的
因为这个题目 c 是单调递增的, 所以可以用单调队列来维护.
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <algorithm>
- #include <queue>
- #include <vector>
- #include <string>
- #define inf 0x3f3f3f3f
- #define inf64 0x3f3f3f3f3f3f3f3f
- using namespace std;
- const int maxn = 1e3 + 10;
- typedef long long ll;
- ll dp[maxn], sum[maxn], c[maxn];
- int que[maxn];
- ll up(int i,int j)
- {
- return dp[i] - dp[j];
- }
- ll down(int i,int j)
- {
- return sum[i] - sum[j];
- }
- ll DP(int i,int j)
- {
- return dp[j] + (sum[i] - sum[j] + 10)*c[i];
- }
- int main()
- {
- int t;
- scanf("%d", &t);
- while(t--)
- {
- int n;
- scanf("%d", &n);
- sum[0] = dp[0] = 0;
- for (int i = 1; i <= n; i++) scanf("%lld%lld", &sum[i], &c[i]), sum[i] += sum[i - 1];
- int head = 0, tail = 0;
- que[tail++] = 0;
- for(int i=1;i<=n;i++)
- {
- while (head + 1 < tail&&up(que[head + 1], que[head]) <= c[i] * down(que[head + 1], que[head])) head++;// 如果满足这个式子
- // 就是说明 que[head+1] 比 que[head] 更优, 所以可以删去这个 que[head] 然后之后不满足这个式子了, 说明 que[head] 比 que[head+1] 更优
- // 说明这个时候的队首就是最优的, 就可以跳出循环
- dp[i] = DP(i, que[head]);
- while (head + 1 < tail&&up(i, que[tail - 1])*down(que[tail - 1], que[tail - 2]) <= up(que[tail - 1], que[tail - 2])*down(i, que[tail - 1])) tail--;
- que[tail++] = i;
- }
- printf("%lld\n", dp[n]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3166076.html