noip2017

noip

DAY1T1小凯的疑惑

我是往余数上考虑的。考虑怎样凑出余数1.

DAY1T2时间复杂度

模拟，关键是不能漏情况。

DAY1T3

DAY2T1

DAY2T2宝藏

非常好的一道状压。与图的结合更是大大增加了题的难度。首先可以发现挖的路一定构成树，然后系数K就是把免费屋当成深度为0的根的树的深度。于是就需要一层一层的转移。预处理几个辅助数组。
注意INF的值，不然会爆。dp[i][s]表示当前在第i层，经过的点的集合是s的最小花费。
https://blog.csdn.net/phantomagony/article/details/78702573

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N=13;
const int M=(1<<12)+10;
const ll inf=0x3f3f3f3f;
ll n,m,a,b,c,ans=1e15;
ll g[N][N],init[N][M],cover[M][M],dp[N][M];
int main(){
//  freopen("a.txt","r",stdin);
    memset(g,inf,sizeof(g));
    memset(init,inf,sizeof(init));
    memset(cover,inf,sizeof(cover));
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;++i) g[i][i]=0;
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&a,&b,&c);
        a--;b--;
        g[a][b]=min(g[a][b],c);
        g[b][a]=min(g[b][a],c);
    }
    ll t=(1<<n)-1;
    for(int i=0;i<n;++i)
        for(int j=0;j<=t;++j)
        //  if((j&(1<<i))==0)
            for(int k=0;k<n;++k)
                if(j&(1<<k))
                    init[i][j]=min(init[i][j],g[i][k]);
    for(int i=0;i<=t;++i){
        int C=i^t;//
        for(int s=C;s;s=(s-1)&C){
            ll tmp=0;
            for(int j=0;j<n;++j)
                if(s&(1<<j))
                    tmp+=init[j][i];
                if(tmp<inf) cover[s][i]=min(cover[s][i],tmp);
        }
    }
    for(int i=0;i<n;++i){
        memset(dp,inf,sizeof(dp));
        dp[0][(1<<i)]=0;
        for(int j=1;j<n;++j)
            for(int ss=1;ss<=t;++ss){
                if(dp[j-1][ss]>=inf) continue;
                int C=ss^t;
                for(int s=C;s;s=(s-1)&C)
                    dp[j][s|ss]=min(dp[j][s|ss],dp[j-1][ss]+j*cover[s][ss]);    
            }   
        for(int j=0;j<n;++j)    ans=min(ans,dp[j][t]);
    }
    printf("%lld\n",ans);
    return 0;
}

DAY2T3