T1 money
没错就是原题[NOI2018提高组]货币系统
这必然是一道完全背包
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 110
#define maxm 25010
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int T,n,a[maxn];
int flag[maxm],ans,maxx;
void pre(){
memset(a,0,sizeof(a));
memset(flag,0,sizeof(flag));
ans=0;maxx=0;
}
int main(){
// freopen("money.in","r",stdin);
// freopen("money.ans","w",stdout);
read(T);
for(int t=1;t<=T;t++){
pre();
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++){
maxx=max(maxx,a[i]);
flag[a[i]]=1;
}
sort(a+1,a+n+1);
for(int i=1;i<=maxx;i++){
if(flag[i]==0) continue;
int res=maxx-i;
for(int j=1;j<=n;j++){
if(a[j]>res) break;
flag[i+a[j]]=2;
}
}
for(int i=1;i<=maxx;i++) if(flag[i]==1) ans++;
cout<<ans<<endl;
}
return 0;
}
/*
2
4
3 19 10 6
5
11 29 13 19 17
*/
//2
//5
T2 happiness
题面
没有部分分/jk
solution 1
既然n很小，那我们不妨暴搜
要注意的小细节：
- 每组数据都要清零cnt，不然一直++结果就变得十分奇怪
- 输出格式有亿点点坑人，除了要
Scenario #%d:还要注意空行！
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 30
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int T,n,c1,c2,a[maxn];
int cnt,sum,c[maxn];
bool flag=0;
void dfs(int x,int cntt){
if(!x) {flag=1; return ;}
for(int i=1;i<=2*cntt;i++){
if(c[i]>=a[x]){
c[i]-=a[x];
dfs(x-1,cntt);
c[i]+=a[x];
}
}
}
int main(){
// freopen("happiness2.in","r",stdin);
read(T);
for(int t=1;t<=T;t++){
read(n),read(c1),read(c2);
if(c1>c2) swap(c1,c2);
for(int i=1;i<=n;i++) read(a[i]);
sort(a+1,a+n+1);
cnt=0;//********
while(1){
cnt++;
flag=0;
for(int i=1;i<=cnt;i++) c[i]=c1;
for(int i=cnt+1;i<=2*cnt;i++) c[i]=c2;
dfs(n,cnt);
if(flag){
printf("Scenario #%d:
%d
",t,cnt);
break;
}
}
}
return 0;
}
/*
2
6 12 13
3 9 13 3 10 11
7 1 100
1 2 33 50 50 67 98
//
Scenario #1:
2
Scenario #2:
3
*/
哦对，想要优化可以二分的，但是其实不用二分也能过
solution 2
Whisper_Rain巨佬用的状压，tql%%%
大概意思应该是枚举子集，因为我们不关心哪辆车到底运了啥，只知道要运什么就可以了，所以还能有一个优化（具体的记不清了QAQ
码就不放了因为不会写
T3 treasure
题面
换根DP经典题
只需要注意下换根DP的2147483647个小细节就可以了
以及cincout大数据输入输出事真的爽
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 300010
using namespace std;
template<typename T>
inline void read(T &x){
x=0;bool flag=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n,x,y,z,a[maxn];
int cnt=1,head[maxn],f[maxn],g[maxn],h[maxn],pos[maxn];
bool vis[maxn];
struct node{
int nxt;
int to;
int v;
}e[2*maxn];
void add(int from,int to,int v){
e[++cnt].to=to;
e[cnt].nxt=head[from];
head[from]=cnt;
e[cnt].v=v;
}
void dfs1(int x,int fa){//先跑一遍树形DP
f[x]=g[x]=a[x];
if(vis[x]) return ;
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to,v=e[i].v;
if(y==fa) continue;
dfs1(y,x);
f[x]+=max(f[y]-2*v,0);
}
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to,v=e[i].v;
if(y==fa) continue;
if(g[y]>v){
int res=f[x]+g[y]-v-max(f[y]-2*v,0);
if(res>g[x]){
h[x]=g[x];
g[x]=res;
pos[x]=y;
}
else h[x]=max(h[x],res);
}
}
}
void dfs2(int x,int p,int val){//换根DP
int yp=e[p].to,vp=e[p].v;
int t=max(f[yp]-2*vp,0);
int res=f[x]-vp+val;
f[x]+=t;
g[x]+=t;
if(res>g[x]){
h[x]=g[x];
g[x]=res;
pos[x]=yp;
}
else h[x]=max(h[x],res);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to,v=e[i].v;
if(i==p) continue;
int tmp=max(f[y]-2*v,0);
int vall=((y==pos[x])?h[x]:g[x])-tmp;
f[x]-=tmp;
dfs2(y,i^1,vall);
f[x]+=tmp;
}
}
int main(){
read(n);
for(int i=1;i<=n-1;i++){
read(x),read(y),read(z);
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=n;i++) read(a[i]);
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++) printf("%d
",g[i]);//宁阔以试试cout大数据输出，一定很爽
return 0;
}
/*
6
1 2 1
2 3 3
3 4 36
3 6 13
3 5 2
6 8 9 10 13 1
//
30
29
28
10
30
16
*/