ToB企服应用市场:ToB评测及商务社交产业平台

标题: AGC004B Colorful Slimes [打印本页]

---

作者: 西河刘卡车医    时间: 2023-11-5 23:18
标题: AGC004B Colorful Slimes
$ {\scr \color {Orchid}{\text{生于尘埃，溺于人海，死于理想高台。}}} $

题目链接:Colorful Slimes

$ {\scr \color {Cyan}{\text{Solution}}} $

分析

思路：挺神奇的$dp$
一个比较显然的结论：最小值的方案中第$2$种操作最多用$n-1$次
证明大概就是一个数用$n-1$次一定会变成另一个数
下面说说$dp$的思路：
$dp[j]$表示能用最多$j$次第$2$种操作能变成$a_i$的最小值
假设$a_k$所有可以用最多$j$次第$2$种操作能变成$i$的最小值，则$dp[j]=a_k$
举个栗子：

1. 3 1 4

复制代码

对于这个$4$来说，用最多$2$次操作能变成坐标为$3$的数最小值，就是$1$
 
如果能理解定义了，那我们接着往下看：
$dp$递推其实并不难，取个$min$比较就行
统计答案怎么做？
我们可以枚举用了几次$2$的操作，后直接相加$dp[1...n][j]$即可
这也是为什么定义方程是“用了j次及以下”的关键qwqq
Code:

[code]//From:201929#include#define L long longusing namespace std;L a[2005],dp[2005][2005];int main(){    int n;    L x;    scanf("%d%lld",&n,&x);    for(int i=1;i

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4