5.26模拟赛

DP专题

A 货币系统

NOIP2018原题 完全背包裸题

码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define re register
using namespace std;
const int INF=0x3f3f3f3f,N=110,M=25010;

inline int read(){
	int x=0,y=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}

int t,n,a[N],f[M],maxx=0,ans=0;

int main(){

	// freopen("money.in","r",stdin);
	// freopen("money.ans","w",stdout);
	
	t=read();
	while(t--){
		n=read();
		ans=n;
		memset(f,-INF,sizeof f);
		maxx=0;
		for(int i=1;i<=n;i++) a[i]=read(),maxx=max(maxx,a[i]),f[a[i]]=1;
		sort(a+1,a+1+n);
		for(int i=1;i<=n;i++){
			for(int j=a[i];j<=maxx;j++){
				int o=f[j];
				f[j]=max(f[j],f[j-a[i]]+1);
				
			}
		}
		for(int i=1;i<=n;i++) if(f[a[i]]>1) ans--;
		printf("%d\n",ans);
	}
	
	
	// fclose(stdin);
	// fclose(stdout);

    return 0;
}

B happiness

不可做

题意：有两辆有体积的车，同时来回，有一些物品有体积，问最少走多少趟能把所有物品转移

听说可以用状压，但是我不会，等dalao来教，我只会二分答案用dfs判断（其实二不二分对复杂度也没啥影响，n太小了

码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f,N=110,S=1100;

int t;

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

namespace work{
    int n,c1,c2,a[N],c[2*N],flag=0;
    void clear(){
        n=0,c1=0,c2=0;
        flag=0;
        memset(a,0,sizeof a);
    }
    void readin(){
        n=read();
        int c,b;
        c=read();
        b=read();
        c1=min(c,b);
        c2=max(c,b);
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
    }

    void dfs(int x,int cnt){
        if(!x){flag=1;return;}
        for(int i=1;i<=cnt*2&&!flag;i++){
            if(c[i]>=a[x]) c[i]-=a[x],dfs(x-1,cnt),c[i]+=a[x];
        }
    }

    bool check(int i){
        flag=0;
        for(int j=1;j<=i;j++) c[j]=c1;
        for(int j=i+1;j<=2*i;j++) c[j]=c2;
        dfs(n,i);
        if(flag){
            return 1;
        }
        return 0;
    }

    void sswork(int k){
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        printf("Scenario #%d:\n%d\n\n",k,l);
    }
    
}

int main(){

    t=read();
    int k=1;
    while(t--){
        work::clear();
        work::readin();
        work::sswork(k++);
    }
    
    return 0;
}

C 宝藏

题意：给个树，边有边权，点有点权，每次经过一条边贡献是\(-w\)，第一次经过一个点贡献是\(val\)，问从每个节点出发的最大贡献是多少

明显的换根DP，但是连根节点的DP都不会，考场上推柿子的时候考虑了三种情况，一种是从待更新的子树走到已更新的子树里，一种是从已更新的子树走到待更新的子树里，一种是只走待更新的子树，期望50，但是读取到20，考完了一想，只用记录从根节点走到待更新的子树里考虑回不回来就可以了，还简单，菜死了

抄的std不知道啥意思

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f,N=3000100;

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

int e[N],ne[N],h[N],w[N],idx=2;
int f1[N],v[N],pos[N],f2[N],f3[N],f4[N];
int n;

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int x,int fa){
    f1[x]=f2[x]=v[x];
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        dfs(j,x);
        f1[x]+=max(f1[j]-(w[i]<<1),0);
    }
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(f2[j]-w[i]>0&&j!=fa){
            int tmp=max(f1[j]-(w[i]<<1),0);
            int s=f1[x]-tmp+f2[j]-w[i];
            if(s>f2[x]){
                f3[x]=f2[x];
                f2[x]=s;
                pos[x]=j;
            }else f3[x]=max(f3[x],s);
        }
    }
}

void dfsexroot(int x,int u,int val){
    int j=e[u^1];
    int t=max(f1[j]-(w[u]<<1),0);
    int s=f1[x]+val-w[u];
    f1[x]+=t,f2[x]+=t;
    if(s>f2[x]){
        f3[x]=f2[x];
        f2[x]=s;
        pos[x]=j;
    }else f3[x]=max(f3[x],s);
    for(int i=h[x];~i;i=ne[i]){
        if(i!=(u^1)){
            int k=e[i];
            int tmp=max(f1[k]-(w[i]<<1),0);
            f1[x]-=tmp;
            dfsexroot(k,i,(pos[x]==k?f3[x]:f2[x])-tmp);
            f1[x]+=tmp;
        }
    }
}

int main(){

    memset(h,-1,sizeof h);

    n=read();
    for(int i=1;i<n;i++){
        int a,b,c;
        a=read(),b=read(),c=read();
        add(a,b,c);
        add(b,a,c);
    }

    for(int i=1;i<=n;i++) v[i]=read();

    dfs(1,0);

    dfsexroot(1,0,0);
    
    for(int i=1;i<=n;i++) printf("%d\n",f2[i]);
    return 0;
}