2016 SCUT 专题训练简单dp

2019-11-09 19:36:38

字体：大中小

来源：转载

供稿：网友

Link：https://vjudge.net/contest/112698#overview

E - 搬寝室 HDU - 1421

从n件物品中搬走2*k 种，每次搬两件，消耗的体力是两手物品重量差的平方，对物品按重量排序之后，可以证明：搬相邻重量的物品才能消耗最少，abcd四件物品重量非严格递增，先搬bc再搬ad消耗的体力一定不会比先搬ab再搬cd小。很容易推出来的。所以dp[k][n]表示从前n个物品了搬了k对物品的体力消耗最小值，

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,k;int p[2005];int dp[1005][2005];//第k对物品，前n个里面的最小值int main(){ int a, b; while (~scanf("%d%d", &n,&k)){ memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++){ scanf("%d", &p[i]); } sort(p + 1, p + 1 + n); for (int i = 0; i <= n; i++){ dp[0][i] = 0; } for (int i = 1; i <= k; i++){ for (int j = 2 * i; j <= n; j++){ dp[i][j] = min(dp[i - 1][j - 2] + (p[j] - p[j - 1])*(p[j] - p[j - 1]), dp[i][j - 1]); } } PRintf("%d/n", dp[k][n]); } return 0;}

F - Humble Numbers HDU - 1058

因子包含2,3,5,7的数称为humble number，要求第n个humble number。就需要地推出这个数列，具体的递推方法见代码，细节要注意。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int a, b, c, d,n;int ans[5843];int main(){ a = b = c = d = 1; ans[1] = 1; int cnt = 1; while (cnt != 5842){ ans[++cnt] = min(min(ans[a] * 2, ans[b] * 3), min(ans[c] * 5, ans[d] * 7)); if (ans[cnt] == ans[a] * 2)a++; else if (ans[cnt] == ans[b] * 3)b++; else if (ans[cnt] == ans[c] * 5)c++; else d++; if (ans[cnt] == ans[cnt - 1]){ cnt--; } } while (scanf("%d", &n), n != 0){ int m = n / 10 % 10; if (m != 1 && n % 10 == 1){ printf("The %dst humble number is %d./n", n, ans[n]); } else if (m != 1 && n % 10 == 2){ printf("The %dnd humble number is %d./n", n, ans[n]); } else if (m != 1 && n % 10 == 3){ printf("The %drd humble number is %d./n", n, ans[n]); } else{ printf("The %dth humble number is %d./n", n, ans[n]); } } return 0;}

G - Max Sum HDU - 1003

求子序列最大和，因为可能出现全为负数的情况，所以处理方法要注意数据范围和细节。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n;int num[100005];int main(){ int t; scanf("%d", &t); for (int k = 1; k <= t; k++){ scanf("%d", &n); for (int i = 1; i <= n; i++){ scanf("%d", &num[i]); } int beg = 1, end = 1, max = -1001; int cntbeg = 1; int cnt = 0; for (int i = 1; i <= n; i++){ if (num[i]>cnt&&num[i]>num[i] + cnt){ cnt = num[i]; cntbeg = i; } else{ cnt += num[i]; if (cnt < -1000){ cntbeg = i + 1; cnt = 0; continue; } } if (cnt>max){ max = cnt; beg = cntbeg; end = i; } } printf("Case %d:/n", k); printf("%d %d %d/n", max, beg, end); if (k < t){ printf("/n"); } } return 0;}

L - I NEED A OFFER! HDU - 1203

背包的变种，求获得offer的最大概率应该装变成求没得到offer的最小概率，计算也变得容易了，只需要简单相乘。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,v;double p[10005];int need[10005];double dp[10005];int main(){ while (scanf("%d%d", &v, &n), v + n){ for (int i = 1; i <= n; i++){ scanf("%d%lf", &need[i], &p[i]); p[i] = 1 - p[i]; } for (int i = 0; i <= v; i++)dp[i] = 1; for (int i = 1; i <= n; i++){ for (int j = v; j >= need[i]; j--){ dp[j] = min(dp[j - need[i]] *p[i], dp[j]); } } printf("%0.1f%%/n", (1 - dp[v]) * 100); } return 0;}

M - 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活 HDU - 2191

比较经典的多重背包，用的是将每种物品的n件转换成不同的物品。

#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>using namespace std;int n,m;int pri[105];int wei[105];int many[105];//int used[105];int dp[105];//前n个物品int main(){ int t; scanf("%d", &t); while (t--){ scanf("%d%d", &m, &n); for (int i = 1; i <= n; i++){ scanf("%d%d%d", &pri[i], &wei[i], &many[i]); } int ans = 0; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++){ int cntn = many[i]; for (int j = 1; j < cntn; j <<= 1){ cntn -= j; for (int k = m; k >= j*pri[i]; k--){ dp[k] = max(dp[k], dp[k - j*pri[i]] + j*wei[i]); } } for (int k = m; k >= cntn*pri[i]; k--){ dp[k] = max(dp[k], dp[k - cntn*pri[i]] + cntn*wei[i]); } } printf("%d/n", dp[m]); } return 0;}

上一篇：PerformanceCounter 基本介绍以及示例方法

下一篇：EXCEL排序（结构体二级排序）