OI周赛15

B-三角形：动态规划O(n*m*10000)

大意：
给n个背包，第i个背包有mi个物品的价值，从这n个背包中各取一个物品，总价值为这n个物品的价值和，求总价值前k的总价值和。
思路：
从背包中取物品，每个背包中的物品必取一个，由此联想的用dp来做。
先找状态：因为要求总价值前k的和，并且从数据上看来，一次选完后总价值不会超过10000，那就从1-10000判断能否组合出来，能组合出来又有多少种组合方式。所有问题就变成了组合成某个数的方法数。
                  所有找到状态有dp[i][j] 表示前i个背包种获得价值为j的方法数。
状态转移：dp[i][j] = dp[i-1][j-x]
初值：dp[0][0] = 1 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int dp[105][10005];//dp[i][j]前i个背包中获得价值为j的种类数 
int main()
{
	int n,k,m,x;
	cin >> n >> k;
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		cin >> m;
		for(int j = 1; j <= m; j++){
			cin >> x;
			for(int t = x; t <= 10000; t++){
				dp[i][t] += dp[i-1][t-x];
			}
		}
	} 
	int cnt = 0;
	int ans = 0;
	for(int i = 1; i <= 10000; i++){
		if(dp[n][i]) {
			if(cnt+dp[n][i] > k){
				ans += (k-cnt)*i;
				break;
	    	}
	    	else{
	    		cnt += dp[n][i];
		    	ans += dp[n][i]*i;
			}
		}
	}
	cout << ans << endl;
 	return 0;
}

OI周赛14

C-tree：树形dp

大意：
给定一个n个节点，n-1条边的树，根节点可以任意选择，求各点深度之和的最小值。
思路：
假设以dp[i]表示以节点i为根节点的深度之和，size[i]表示以i为根节点的子树大小，如果我们已知以某个点u作为根节点的各点深度之和，那么以该点的某个孩子节点v作为根节点的各点深度之和为
dp[v] = dp[u] + n - 2*size[v]，因为孩子节点v的子树上的节点到v的深度为到节点u的深度减一，其它节点深度加一，我们已知节点v的子树的小为size[v]，每个节点深度减一，总共size[v]个节点，所以减去size[v],剩余其它节点为n-size[i]，所以dp[v] = dp[v] - size[v]+n-size[v] = dp[u] + n - 2*size[v]. 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

vector<int>a[1000005];
int size[1000005],h[1000005],n,u,v;
ll dp[1000005],ans = 0;
void dfs1(int s,int f)
{
	int l = a[s].size();
	for(int i = 0; i < l; i++){
		int v = a[s][i];
		if(v == f) continue;
		h[v] = h[s] + 1;
		ans += h[v];
		dfs1(v,s);
		size[s] += size[v];
	}
	size[s] += 1;
}

void dfs2(int s,int f)
{
	ans = min(ans,dp[s]);
	int l = a[s].size();
	for(int i = 0; i < l; i++){
		int v = a[s][i];
		if(v == f) continue;
		dp[v] = dp[s] + n - 2*size[v];
		dfs2(v,s);
	//	ans = min(ans,)
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i < n; i++){
	    cin >> u >> v;
	    a[u].push_back(v);
	    a[v].push_back(u);
	}
	dfs1(1,-1);
	//cout << ans << endl;
	dp[1] = ans;
	dfs2(1,-1);
	cout << ans << endl;
//	for(int i = 1; i <= n; i++){
//		cout << h[i] << " ";
//	}
 	return 0;
}

D-talk：动态规划

https://ac.nowcoder.com/acm/contest/4479/D
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

double f[100005],p[100005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%lf",&p[i]);
	f[0] = 0.0;
	f[1] = 0.0;
	for(int i = 2; i <= n+1; i++){
		f[i] = (f[i-1]+1+(p[i-1]-1)*f[i-2]) / p[i-1];
	}
	printf("%.3lf\n",f[n+1]);
 	return 0;
}