【codeforces 510D】Fox And Jumping

【题目链接】:http://codeforces.com/contest/510/problem/D

【题意】

你可以买n种卡片;

每种卡片的花费对应c[i];

当你拥有了第i种卡片之后;

你可以在任意位置x跳到x-l[i]或x+r[i];

问你至少要花费多少钱买卡片,使得你能够跳跃到坐标轴上的任意一个整数点;

【题解】

有个结论；

直接记下来吧

如果gcd(a,b)==1,那么所有的点就都能跳跃到了;

所以问题就转化为,给你n个长度,让你在这n个长度中选取若干个;

使得它们的gcd为1;

且要求花费的金钱最少;

可以写个DP;

f[x]表示gcd为x的最小花费;

先预处理出单个数字的gcd的最小花费->设为出现的数字的最小花费就好;

然后利用之前出现过的f[x]来更新gcd(x,a[i])的最小花费,即其的f值;

最后看看gcd(1)能不能得到;

能得到就有解;

(在做DP的过程中不能时刻保证f[x]就是gcd为x的最小花费,但自己想想就能明白最后肯定是gcd为x的最小花费,因为gcd求的顺序不分先后的。)

【Number Of WA】

0

【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

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

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) cin >> x

#define pri(x) cout << x

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 310;

const int INF = 21e8;

int n,l[N],c[N];

map<int,int> f;

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false);

    rei(n);

    rep1(i,1,n)

        rei(l[i]);

    rep1(i,1,n)

        rei(c[i]);

    rep1(i,1,n)

    {

        if (!f[l[i]]) f[l[i]] = INF;

        f[l[i]] = min(f[l[i]],c[i]);

    }

    rep1(i,2,n)

    {

        for (pii x:f)

        {

            int pre = x.fi;

            int xin = __gcd(pre,l[i]);

            if (!f[xin]) f[xin] = INF;

            f[xin] = min(f[xin],x.se+c[i]);

        }

    }

    if (!f[1])

        return pri(-1),0;

    else

        pri(f[1]);

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}

秒客网

【codeforces 510D】Fox And Jumping

相关文章