Day1
|
题目名称 |
party |
array |
treasure |
|
输入 |
party.in |
array.in |
treasure.in |
|
输出 |
party.out |
array.out |
treasure.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
内存限制 |
64MB |
64MB |
64MB |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
是否有部分分 |
无 |
无 |
无 |
|
题目类型 |
传统 |
传统 |
传统 |
party
题目描述：
在M公司里，每个人只有一个直属上司(除了boss)。这个公司举办派对，每个人可以给派对带来一定的欢乐值，但是每个人不能和自己的上司同时参加这个派对，求派对的最大欢乐值。
输入：
第一行n表示公司有n个人。
第二行n个数，表示每个人的上司是谁，如果这个人的上司为0，说明这个人是boss。
第三行n个数，表示每个人的欢乐值为wi。
输出：
一行一个数表示最大欢乐值。
样例输入：
6
0 1 1 1 4 4
1 1 1 1 1 1
样例输出：
4
解释：2 3 5 6 同时出席。
数据规模:
对于30%的数据,n<=20。
对于100%的数据，n<= 1000000,0<=w[i]<=1000。
题解：树形dp,dp[i][0/1]表示i号节点来不来，若父亲来，儿子肯定不来，若父亲不来，儿子随便来不来；
dp[i][0] = sum( max (dp[son[i]][0], dp[son[i]][1]); dp[i][1] = sum(dp[son[i]][0]);
#include<bits/stdc++.h> using namespace std; const int maxn = 1000005; int head[maxn],tot,dp[maxn][2]; struct edge{ int to,nxt; }G[maxn + 100]; void add(int u,int v){ G[++tot].nxt = head[u]; G[tot].to = v; head[u] = tot; } void dfs(int u, int f){ for(int i = head[u]; i; i = G[i].nxt){ int v = G[i].to; //if(v == f)continue; dfs(v, u); dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][0], dp[v][1]); } } int main(){ freopen("party.in","r",stdin); freopen("party.out","w",stdout); int n; scanf("%d",&n); for(int i = 1; i <= n; i++){ int fa; scanf("%d",&fa); add(fa, i); } for(int i = 1; i <= n; i++){ int w; scanf("%d",&w); dp[i][1] = w; } dfs(0, 0); cout<<dp[0][0]<<endl; }
array
题目描述：
给定两个长度为n的排列p1和p2，求它们的最长公共子序列。
输入：
第一行一个数n。
接下来两个n个数分别表示p1和p2。
输出:
一个数表示最长子序列的长度。
样例输入：
3
1 2 3
2 1 3
样例输出：
2
解释及说明：
共有两种方案，分别为子序列为13和子序列为23.
数据规模：
对于30%的数据，n<=2000.
对于100%的数据,n<=100000。
题解：由于是排列，所以上下元素一样，且一个序列中无重复元素，我们就把一个序列的元素顺序做一个映射，在第二个序列中作最长上升子序列
#include<bits/stdc++.h> using namespace std; const int maxn = 1000005; int d[maxn], mp[maxn], q[maxn], tail; int main(){ freopen("array.in","r",stdin); freopen("array.out","w",stdout); int n, a, b; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%d",&a); mp[a] = i; } for(int j = 1; j <= n; j++){ scanf("%d",&b); d[j] = mp[b]; } for(int i = 1; i <= n; i++){ if(d[i] > q[tail])q[++tail] = d[i]; else { int pos = lower_bound(q + 1, q + 1 + tail, d[i]) - q; q[pos] = d[i]; } } cout<<tail<<endl; }
treasure
题目描述：
小a可以攻打m座城堡，攻打每个城堡有不同的宝物，但是在攻打有些城堡前，需要攻打另外的城堡。小a想知道，能获得的最多宝物是多少？
输入：
第一行两个数，n,m。分别表示有n个城堡，可以攻打m个。
接下来n行每行两个数a,b，分别表示在攻打第i个城堡前需要攻打a，攻打后获得b的宝物。
输出：
一行一个数ans表示可以获得的最大宝物数量。
样例输入
3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0
样例输出:
5
13
数据规模：
对于30%的数据，n<=20，m<=20。
对于100%的数据，n<=500，m<=500,b[i]<=1000。
题解：树形DP，这道题很像树上染色，但不用考虑子树和外界 联系，要简单一点；
dp[i][j]表示给i为根的子树分配j次攻打机会可获得最大的利益，答案就为dp[root][m];
由于必须打父亲，才能打儿子，所以儿子可分配的机会为j-1,但0号点是我们假设的城堡，故他的子树有j次机会，特判一下，然后做一个分组背包就好了，因为一个子树分配的机会只能有一种方案；
抽象一下：每个子树为一组，可供选择的物品为min(siz[father], j), 容量为min(siz[son],j);
#include<bits/stdc++.h> using namespace std; const int maxn = 505; int n,m; int head[maxn],tot,dp[maxn][maxn],siz[maxn]; struct edge{ int to,nxt,w; }G[maxn + 100]; void add(int u,int v,int w){ G[++tot].nxt = head[u]; G[tot].to = v; G[tot].w = w; head[u] = tot; } void dfs(int u){ for(int i = head[u]; i; i = G[i].nxt){ int v = G[i].to; dfs(v); int V = min(siz[u], m); int K = min(siz[v], m); for(int s = V; s >= 1; s--) for(int j = 1; j <= ( u == 0 ? min(s, K) : min(s-1, K) ); j++){ dp[u][s] = max( dp[u][s], dp[u][s - j] + dp[v][j] + G[i].w); } } } void get_size(int u){ siz[u] = 1; for(int i = head[u]; i; i = G[i].nxt){ int v = G[i].to; get_size(v); siz[u] += siz[v]; } } int main(){ freopen("treasure.in","r",stdin); freopen("treasure.out","w",stdout); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++){ int fa,w; scanf("%d%d",&fa,&w); add(fa, i, w); } get_size(0); dfs(0); cout<<dp[0][m]<<endl; }
考试突然不会分组背包了，╮(╯▽╰)╭， 一定要记得容量放外面，从大到小啊