2017.9.28 NOIP模拟赛

题解 套题

题简单也要静下心来做...

目录

• 2017.9.28 NOIP模拟赛
  • 矩阵
    • 思路
    • 代码
  • 时态同步
    • 思路
    • 代码
  • 葡萄
    • 思路
    • 代码

矩阵

思路

• 就是一个变形的区间DP；
• 除了第一个矩阵，其它的只保留列数，构成一个序列；
• 问题其实就是说，每次可以去掉除两边外的一个数$a_i$，代价是$a_{i-1}\times a_i \times a_{i+1}$，求总代价最小；
• 这样我们考虑正常的区间DP套路，枚举长度、左端点和中间点，则有$dp(l,r)=\min_{k=l+1}^{r-1}\{ dp(l,mid)+dp(mid+1,r)+a_{l-1}\times a_k \times a_r \}$；
• $ans=dp(2,n+1)$，因为这个合并时区间是“右偏”的。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
#include <cstring>
using std::min;
const int MAXN=505;
int n,m;
int a[MAXN];
inline long long DP(){
    static long long dp[MAXN][MAXN];
    for(int len=2;len<=m;++len){
        for(int l=2,r,lim=m-len+1;l<=lim;++l){
            r=l+len-1;
            dp[l][r]=dp[l+1][r]+(long long)a[l-1]*a[l]*a[r];
            for(int mid=l+1;mid<r;++mid)
                dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]+(long long)a[l-1]*a[mid]*a[r]);
        }
    }
    return dp[2][m];
}
int main(){
    setIO("A");
    read(n);
    read(a[++m]),read(a[++m]);
    for(int i=2,tmp;i<=n;++i)
        read(tmp),read(a[++m]);
    write(DP());
    return 0;
}

时态同步

思路

• 这其实是ZJOI 2007原题。。。
• 就是一个简单的贪心，显然选的边越靠上，影响的叶节点越多，就越优；
• 那么一遍DFS，每个节点将其子树中的叶节点加到同步即可。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=5e5+5;
int n,rt;
int he[MAXN];
long long ans;
long long dson[MAXN];
struct line{int to,nex,w;}ed[MAXN<<1];
inline void addE(int u,int v,int w){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
void DFS(int u,int fa,long long d){
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            DFS(v,u,d+ed[i].w);
            dson[u]=max(dson[u],dson[v]+ed[i].w);
        }
    }
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa) ans+=dson[u]-dson[v]-ed[i].w;
    }
}
int main(){
    setIO("B");
    read(n),read(rt);
    for(int i=1,u,v,w;i<n;++i){
        read(u),read(v),read(w);
        addE(u,v,w),addE(v,u,w);
    }
    DFS(rt,0,0);
    write(ans);
    return 0;
}

葡萄

思路

• 虽然数据量不小，但仍是状压DP，复杂度$O(n \times 2^k)$；
• 考虑枚举每$k$个葡萄选的状态，若设二进制从低到高位的是第$1$~$k$个，$mod=(1<<k)-1$，那么现在的状态$j$只能从$j<<1\&mod$和$j<<1\&mod|1$转移而来，这个DP方程就很好写了；
• 但是注意初始化数组。。。要不就AK了

代码

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using std::max;
const int MAXN=10005,MAXSTA=1<<10;
int n,k,a,b,sum;
int cnt[MAXSTA],grape[MAXN];
inline void prepare(){
    for(int i=1,lim=1<<k;i<lim;++i)
        cnt[i]=cnt[i>>1]+(i&1);
}
inline int DP(){
    static int dp[2][MAXSTA];
    memset(dp,-0x3f,sizeof(dp));
    for(int i=0,lim=1<<k,tmp,j;i<lim;++i){
        if(cnt[i]<a || b<cnt[i]) continue;
        dp[k&1][i]=0;
        tmp=i,j=1;
        while(tmp){
            if(tmp&1) dp[k&1][i]+=grape[j];
            tmp>>=1,++j;
        }
    }
    for(int i=k+1,lim=1<<k,mod=lim-1,top=lim>>1;i<=n;++i){
        for(int j=0,tmp,l;j<lim;++j){
            if(cnt[j]<a || b<cnt[j]) continue;
            dp[i&1][j]=max(dp[~i&1][j<<1&mod],dp[~i&1][j<<1&mod|1])+grape[i]*(bool)(j&top);
        }
    }
    int ret=INT_MIN;
    for(int i=0,lim=1<<k;i<lim;++i){
        if(a<=cnt[i] && cnt[i]<=b)
            ret=max(ret,dp[n&1][i]);
    }
    return ret;
}
int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    scanf("%d%d%d%d",&n,&k,&a,&b);
    for(int i=1;i<=n;++i){
        scanf("%d",&grape[i]);
        sum+=grape[i];
    }
    prepare();
    printf("%d",(DP()<<1)-sum);
    return 0;
}