牛客OI周赛
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;
} 
投递快手等公司10个岗位 >
