键盘

发表于 |
字数统计: 344 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※

Description

现有长度为x的序列，以如下操作:

  1. 加 1（消耗 1）
  2. 全选（消耗 2）
  3. 复制（消耗 2）
  4. 粘贴（消耗 2）
  5. 删除（消耗 1） （删除一个或所选择）

求最小消耗使序列变为n

Solution

发现是一个以长度为节点的图，跑最短路即可

Details

  • 删除操作只存在两种，删1或删所有，所以所有大于N的状态可以直接通过现状态推导

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Nn=2*1e6+5;
int X,N,Dist[Nn],Vis[Nn]; queue<int>q;
struct Alpha{
    int id,d;
    friend bool operator<(Alpha a,Alpha b){
        return a.d>b.d;
    }
};
void Bre(int i,int j,int w){
    if(Dist[i]>Dist[j]+w){
        Dist[i]=Dist[j]+w;
        if(!Vis[i]) q.push(i);
    }
}
int main(){
    scanf("%d%d",&X,&N); for(int i=0;i<=N;i++) Dist[i]=0x3f3f3f3f;
    if(X>N){ Dist[0]=3; q.push(0); Vis[0]=1; Dist[N]=X-N;}
    else{Dist[X]=0; Dist[N]=N-X; q.push(X); Vis[X]=1;}
    while(!q.empty()){
        int now=q.front();q.pop();
        if(now<N) Bre(now+1,now,1);
        if(now){
            Bre(now-1,now,1);
            for(int i=1;i*now<=N;i++)
            if(now*(i+1)>N) Bre(N,now,4+2*i+now*(i+1)-N);
            else Bre(now*(i+1),now,i*2+4);
        }
        Vis[now]=0;
    }
    printf("%d\n",Dist[N]);
    return 0;
}