Link：https://vjudge.net/contest/112698#overview
從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]); } } 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;}求子序列最大和，因為可能出現全為負數的情況，所以處理方法要注意數據范圍和細節。
#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;}背包的變種，求獲得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;}比較經典的多重背包，用的是將每種物品的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;}新聞熱點
疑難解答
