洛谷 SCP 2024第二轮（复赛 S 组）模拟 -- T1-商店砍价 题解

$I$. 题面描述

题目 - 商店砍价

$II$. 心路历程

14：00 开始比赛，先看T1。

第一眼贪心：先删 $v_x$ 最小的，然后删的过程中计算剩下数的大小，很显然剩余的数字要在 $5$ 个以内，否则我们可以再删掉一个代价小于 $10^5$ 的数，结果更优。

14：50 敲完以后才发现，$1-9$ 每个数的个数都很多，删的时候删不同的位置结果不同。逐放弃该做法。

15：10 实在想不下去了，开T2。

T2 想出来了一个神奇做法，先降低温度，再对于子树升高温度，并且保证越靠近根节点温度约接近0。

16：30 实现差不多了，但是样例过不了，后来发现有漏洞，不好调，于是放弃。

17：00 该结束了，赶快把T1dfs暴力打上去，喜提 $16pts$ 结束。

$III$. 思路

引理

• 删完后剩余的数字要在 $5$ 个以内。

证明

• 如果删完后剩余的数字不在 $5$ 个以内，那么我们可以再删掉一个数字。因为 $v$ 最大是 $10^5$ ，删除后对结果的贡献小于等于 $10^5$ ，而如果直接把剩余的数字全部删除贡献必定更大，因此这样结果更优。

$24pts$ 做法

dfs，枚举每个数位对答案的贡献是 $v$ 还是和其他的组成小于 $5$ 位数，每个数位有取或不取两种情况，时间复杂度 $O(2^n)$ .

$36pts$ 做法

对于 $24pts$ 的解法，折半搜索即可，时间复杂度 $O(2^{\frac{n}{2}})$ .

$40pts$ 做法

既然数字只有一种，从头开始删就行了。对于第10个测试点时间复杂度为 $O(n)$ .

$100pts$ 做法

考虑优化 $20pts$ 暴力做法。

由于每个数有选和不选两种情况，所以考虑 动态规划,dp 。

定义状态：$f[i][j]$ 表示从前 $i$ 个数中最终保留 $j$ 个数，此时的最小代价。

那么对于每一个位置，都可以保留或直接删除，由 $f[i-1][j]$ 和 $f[i-1][j-1]$ 递归而来即可。

但是我们会发现一个问题：如果保留的话，还需要存储以前保留的数，将其乘上 $10$ 再加上该数字，比较麻烦。

所以我们 倒序遍历，这样如果保留，只需要再加上 $f[i+1][j-1]+10^{j-1}\ast a[i]$ 即可（记第 $i$ 位数字为 $a[i]$)。

为什么要加 $10^{j-1}\ast a[i]$ 而不是 $10^j\ast a[i]$ ?
如果 $j=1$ ，此时保留的话只需要将 $a[i]$ 加上即可，那么此时我们希望乘上 $1$ ，即乘上 $10^0=1$ .

综上，得到状态转移方程：
$$f[i][j]=min(f[i+1][j]+a[i],f[i+1][j-1]+a[i]\ast 10^{j-1})(j>0)$$

$$f[i][j]=f[i+1][j]+a[i](j=0)$$

$IV$. 代码实现

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans,p[7],f[100005][7];
int c,t,v[15];
char s[100005];
int main()
{
cin >> c;
cin >> t;
p[0] = 1;
for (int i=1;i<=6;i++)
{
p[i] = p[i-1]*10;
}
while (t--)
{
ans = 1e16;
scanf("%s",s+1);
n = strlen(s+1);
for (int i=1;i<=n;i++)
{
for (int j=0;j<=6;j++)
{
f[i][j] = 1e16;
}
}
for (int i=1;i<=9;i++)
{
scanf("%d",&v[i]);
}
f[n+1][0] = 0;
for (int i=n;i>=1;i--)
{
for (int j=0;j<=6;j++)
{
if (j == 0)
{
f[i][j] = f[i+1][j]+v[s[i]-'0'];
}
else
{
f[i][j] = min(f[i+1][j]+v[s[i]-'0'],f[i+1][j-1]+(long long)((s[i]-'0')*p[j-1]));
}
if (i == 1) ans = min(ans,f[1][j]);
}
}
cout<<ans<<endl;
}
return 0;
}

$V$. 总结感悟

倒叙DP的思想还是很不错的，整体思路层层递进，dp好题。

原文地址：https://blog.csdn.net/weixin_52163022/article/details/143062601

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！