「THUPC2018」城市地铁规划 / City

题目链接https://loj.ac/problem/6395

题意:略。

思路:因为希望新建的地铁轨道数尽可能的少,又要联通,所以肯定是要构造出一棵树,那么题意就转化为给定每个度数的价值,要求构造一棵树使每个点度数价值之和最大,度数的价值我们可以暴力预处理。看到这种度数与生成树的应该立马联想到prufer序列,由prufer序列我们可以知道序列长度为n-2,且每个点在prufer序列中出现的次数加一就是这个点的度数,且可以唯一构造出一棵树,所以问题转化为一个完全背包的问题,相当于背包容量为n-2我们要用这么多度数去填充这个背包使最后的价值最大。然而我们还要考虑度数为1的情况,因为每个点度数一定是大于等于1的,所以我们先把[2,n-2]的度数的价值减去1的,就不用管那个度数为1的限制了,最后加个n\times v[1]即可。方案直接由dp方程逆推去构造即可,要特判n12的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3000+10;
const int P=59393;
int n,k,i,j,a[15],v[N],f[N];
int main(){
    scanf("%d%d",&n,&k);
    for (i=0;i<=k;i++) scanf("%d",&a[i]);
    for (i=1;i<n;i++){
        int coff=1;
        for (j=0;j<=k;j++){
            (v[i]+=coff*a[j]%P)%=P;
            coff=coff*i%P;
        }
        if (i>1) v[i]-=v[1];
    }
    if (n==1) return printf("0 %d\n",v[0]),0;
    else if (n==2){
        printf("1 %d\n",2*v[1]);
        return puts("1 2"),0;
    }
    for (i=1;i<=n-2;i++){
        for (j=i;j<=n-2;j++){
            f[j]=max(f[j],f[j-i]+v[i+1]);
        }
    }
    printf("%d %d\n",n-1,f[n-2]+n*v[1]);
    int x=n-2,id=0,y=n;
    while (x){
        for (i=1;i<=x;i++)if(f[x-i]+v[i+1]==f[x]){
            x-=i;
            if (++id!=1) printf("%d %d\n",id-1,id);
            else i++;
            for (j=1;j<i;j++) printf("%d %d\n",id,y--);
            break;
        }
    }
    printf("%d %d\n",id,id+1);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注