2019牛客国庆day3-G &CF1238E

给定大小为N的数组a[]，给定M组关系，让你重排a[]，使得sum{M队关系的绝对值之差}最小。首先将a排序，然后依次把a填入数组。

假设i在二进制下有x个1，用dp[i]更新dp[i|(1<<j)]，表示的是，将a[x+1]填在第j个位置。注意到a[]已经排序了，那么a[x]的贡献就是：+之前填的个数*a[x]-没填的个数*a[x]；

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=;

int a[N],p[N],e[N];

ll f[<<N];

int main(){

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF) {

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

            scanf("%d",&a[i]);

        sort(a,a+n); //重排，然后依次填入

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

            e[i]=;

            p[i]=;

        }

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

            int a,b;

            scanf("%d%d",&a,&b);

            a--;b--;

            p[a]|=<<b;p[b]|=<<a;

            e[a]++,e[b]++;

        }

        f[]=;

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

            f[i]=1e12;

            int k=__builtin_popcount(i)-; //表示这一轮填a[k]

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

                if(i&(<<j)) {//表示a[k]填在posj处

                    f[i]=min(f[i],f[i^(<<j)]+1LL*a[k]*(__builtin_popcount(p[j]&i)*-e[j]));

                }

            }

        }

        printf("%lld\n",f[(<<n)-]);

    }

    return ;

}

CF-E：

题意：给定M队关系(ai,bi)，让你重排，使得{关系的位置绝对值之和}最小。

依然是枚举最后一个填谁，那么这一轮的贡献是满足(ai已经填入,bi未填入)的个数。

#include<bits/stdc++.h>

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

using namespace std;

const int maxn=;

char c[maxn]; int dp[maxn],f[][];

int main()

{

    int N,M;

    scanf("%d%d%s",&N,&M,c+);

    memset(dp,0x3f,sizeof(dp));

    rep(i,,N-) f[c[i]-'a'][c[i+]-'a']++,f[c[i+]-'a'][c[i]-'a']++;

    dp[]=;

    rep(i,,(<<M)-){

        int t=;

        rep(j,,M-) {

            if(i&(<<j)){

                rep(k,,M-)

                 if(!(i&(<<k))) t+=f[j][k];

            }

        }

        rep(j,,M-) if(!(i&(<<j))) dp[i|(<<j)]=min(dp[i|(<<j)],dp[i]+t);

    }

    printf("%d\n",dp[(<<M)-]);

    return ;

}

巴特西

2019牛客国庆day3-G &CF1238E

最新文章

热门文章