CodeForces 1082 F Speed Dial

题目传送门

题意：现在有n个电话号码，每个电话号码为si，拨打次数为pi。现在有k 个快捷键，每次拨打号码之前可以先按一次快捷键，然后再输入数字，现在问输入数字次数是多少。快捷键的号码可以不在电话簿上。

题解：

先构建一个字典树，然后在字典树上进行DP。

dp[x][rem][fa] x -> 节点x rem -> 还有rem次快捷键次数 fa 最近的那个父亲用了这个快捷键

dp2[x][rem][fa][i] 前面和上面一样 i代表的是处理到i这个节点的最优花费。

dp[x][rem][fa]为可以包含x的最优花费。

dp2[x][rem][fa][i]为不可以包含x的最优花费。

转移方式：

1. 当rem > 1的时候我们可以用 dp[x][rem-1][x] 转移到 dp[x][rem][fa]

2. 对于 dp2[x][rem][fa][i] 我们可以用 dp2[x][rem-j][fa][i+1] + dp[ch[i]][j][fa] 转移过来。

3. 对于 dp[x][rem][fa][i] 我们可以用 dp[2][x][rem][0] + (deep[x] - deep[fa]) * cnt[x] 转移过来。

简单的来说，就是对以x为根的树来说，我们可以用子树上的状态转移过来。

需要注意的有2个点：

1 记忆化转移，因为会有很多的点的状态是重复的。

2 先把小次数的算出来，因为在大次数的转移的过程中需要用的小次数的值。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

struct Node{

    int son[];

    int deep;

    int cnt;

    Node(){

        memset(son, -, sizeof(son));

        cnt = deep = ;

    }

}Trie[];

int dp[][][];

int dp2[][][][];

char s[N];

int tot = ;

void add(){

    int now = , cnt;

    scanf("%s%d", s, &cnt);

    int len = strlen(s);

    for(int i = ; i < len; ++i){

        int to = s[i] - '';

        if(Trie[now].son[to] == -){

            Trie[now].son[to] = ++tot;

            Trie[tot].deep = Trie[now].deep + ;

        }

        now = Trie[now].son[to];

    }

    Trie[now].cnt += cnt;

}

int dfs(int x, int rem, int fa){

    if(dp[x][rem][fa] != -) return dp[x][rem][fa];

    dp[x][rem][fa] = inf;

    if(rem) dp[x][rem][fa] = min(dfs(x, rem-, x), dp[x][rem][fa]);

    vector<int> ch;

    for(int i = ; i < ; ++i)

        if(Trie[x].son[i] != -)

            ch.pb(Trie[x].son[i]);

    dp2[x][rem][fa][ch.size()] = ;

    for(int i = int(ch.size())-; i >= ; --i){

        for(int j = ; j <= rem; ++j){

            dp2[x][rem][fa][i] = min(dp2[x][rem][fa][i], dp2[x][rem-j][fa][i+] + dfs(ch[i], j, fa));

        }

    }

    dp[x][rem][fa] = min(dp[x][rem][fa], dp2[x][rem][fa][]+Trie[x].cnt*(Trie[x].deep - Trie[fa].deep));

    return dp[x][rem][fa];

}

int main(){

    int n, k;

    scanf("%d%d", &n, &k);

    for(int i = , v; i <= n; ++i)

        add();

    memset(dp, -, sizeof(dp));

    memset(dp2, inf, sizeof(dp2));

    int ans = dfs(,k,);

    cout << ans << endl;

    return ;

}

巴特西

CodeForces 1082 F Speed Dial

最新文章

热门文章