SICAU-OJ：要我唱几首歌才能够将你捕捉

要我唱几首歌才能够将你捕捉

题意：

有N种颜色的牛，现在可以执行以下两种操作：

1.抓捕一只牛，代价为ai； 2.花费x的代价使用魔法，让所有颜色加1，N会变为1。

求得到N种颜色的牛最少花费的代价。

题解：

这题挺巧妙的，我一开始想的是贪心，找到每头牛最好从哪头牛更新过来，后来就WA了很多次...因为对施用魔法的情况不能很好地处理。

其实这题可以想：每种颜色的产生都需要一开始选取一头牛，并且经过X次魔法操作（0<=X<=N-1）才行，这里是关键。

根据上面，我们可以得知对于两种颜色i，j，假定他们分别从a，b转移过来，那么通过max(j-b,i-a)次魔法操作肯定可以从a，b转移到i，j。

假定我们现在最多使用k次魔法并且已经得知了每种颜色从哪个位置转移过来，那么现在肯定使用k次魔法可以得到目前的最小结果（可以模拟一下，有些转移我们并不一定需要把k次魔法用完，但有些可能就需要，这样的话就能对施用魔法的情况进行一个好的处理了）。

所以我们可以枚举使用魔法的次数（限定之）为k，我们每头牛最多就只能从[i-k,i]中ai的最小值更新过来，最后统计结果就好了。

这里不可能存在这种情况：相同位置的牛用相同的魔法次数。所以可以保证贪心策略的正确性。

代码如下：

#include <bits/stdc++.h>

#define INF 99999999999999999

using namespace std;

typedef long long ll;

const int N = ;

ll a[N];

ll minx[N][N];

ll n,x;

int main(){

    scanf("%I64d%I64d",&n,&x);

    for(int i=;i<=n;i++) scanf("%I64d",&a[i]);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) minx[i][j]=INF;

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

        ll t=INF;

        for(int j=i;j<=n;j++){

            t=min(a[j],t);

            minx[i][j]=t;

        }

    }

    ll ans=INF;

    for(int k=;k<=n-;k++){

        ll tmp=;

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

            int now=i-k;

            if(now<){

                now+=n;

                tmp+=min(minx[][i],minx[now][n]);

            }else tmp+=minx[now][i];

        }

        ans=min(ans,tmp+(ll)k*x);

    }

    cout<<ans;

    return ;

}

巴特西

SICAU-OJ：要我唱几首歌才能够将你捕捉

最新文章

热门文章