Codeforces 1154F - Shovels Shop - [DP]

题目链接:https://codeforces.com/contest/1154/problem/F

题解:

首先,可以确定的是:

  1、$(x,y)$ 里 $x>k$ 的都不可能用;

  2、肯定买的是 $n$ 个铲子里,价格前 $k$ 小的铲子。

然后,我们用 $f[i]$ 表示买前 $i$ 个铲子,最多可以优惠掉多少钱。

我们假设 $g[x]$ 代表买 $x$ 个铲子,最多可以不用付 $g[x]$ 个铲子的钱。得到状态转移方程:

$f[i] = \min_{j=0}^{i-1}(f[j]+\sum_{k=j+1}^{j+g[i-j]} a[k] )$

换句话说,对于 $f[i]$,我们遍历所有的 $j \in [0,i)$:

  此时,我们前 $j$ 个铲子,最多优惠掉了 $f[j]$ 的钱,那么 $(j+1) \sim i$ 这 $i-j$ 个铲子,我们直接用 $g[i-j]$ 的优惠,省掉这 $i-j$ 个铲子里最便宜的 $g[i-j]$ 个铲子的钱。这样,我们就得到了一种买前 $i$ 个铲子的方案。(至于怎么求 $f[i]$,即维护所有 $j$ 对应的方案中,省钱最多的那一个方案即可。)

  那为什么不用 $g[i-j-1],g[i-j-2],\cdots$ 这些优惠呢?因为假设用这些优惠能省钱更多,那么由于 $f[i]$ 是递增的,所以“$f[j+1]$ 加上用 $g[i-(j+1)]$ 的省钱量”,肯定优于,“$f[j]$ 加上用 $g[i-j]$ 的省钱量”。而“$f[j+1]$ 加上用 $g[i-(j+1)]$ 的省钱量”会在下一个 $j$ 被算到,所以不影响正确性。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn=2e5+;
const int maxk=2e3+; int n,m,k;
int a[maxn],s[maxn];
int g[maxk];
int f[maxk]; int main()
{
cin>>n>>m>>k;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x<=k) g[x]=max(g[x],y);
}
sort(a+,a+n+);
for(int i=;i<=k;i++) s[i]=s[i-]+a[i];
for(int i=;i<=k;i++)
{
f[i]=;
for(int j=;j<i;j++)
f[i]=max(f[i],f[j]+s[j+g[i-j]]-s[j]);
}
cout<<s[k]-f[k]<<endl;
}
上一篇:codeforces#525 Div2---ABC


下一篇:【翻译自mos文章】oracle支持在RDBMS HOME 下的 符号链接( Symbolic Links)吗?