Jun 13 学习笔记
15 Jun 2018学习笔记
UVa 242
题目
Philatelists have collected stamps since long before postal workers were disgruntled. An excess of stamps may be bad news to a country’s postal service, but good news to those that collect the excess stamps. The postal service works to minimize the number of stamps needed to provide seamless postage coverage. To this end you have been asked to write a program to assist the postal service. Envelope size restricts the number of stamps that can be used on one envelope. For example, if 1 cent and 3 cent stamps are available and an envelope can accommodate 5 stamps, all postage from 1 to 13 cents can be “covered”
Output one line for each data set giving the maximal no-gap coverage followed by the stamp denominations that yield that coverage in the following format:
max coverage = < value >: < denominations >
思路
动态规划 完全背包
用d[i]表示能组成i邮资的最小邮票数量。
代码
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#define cur dp[i]
using namespace std;
const int INF = 1e4;
const int maxs = 11;
const int maxn = 11;
const int maxval = 1100;
int S;
int N;
int num[maxn];
int denom[maxn][maxs];
int coverage[maxn];
int dp[maxval];
int solve(int probnum) {
int ans = 0;
memset(dp, INF, sizeof(dp));
// printf("init\n");
for(int i = 0; i < num[probnum]; i++) {
dp[denom[probnum][i]] = 1;
// printf("%d ", dp[denom[probnum][i]]);
}
for(int i = 1;; i++) {
if(dp[i] > S)
return ans = i - 1;
for(int j = 0; j < num[probnum]; j++)
dp[i + denom[probnum][j]] = min(dp[i + denom[probnum][j]], cur + 1);
}
return ans;
}
int main() {
while(scanf("%d", &S) && S) {
// input
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%d", &num[i]);
for(int j = 0; j < num[i]; j++) {
scanf("%d", &denom[i][j]);
// printf(" %d", denom[i][j]);
}
}
// printf("input complete\n");
// printf("%d", denom[0][0]);
int maxcoverage = -1;
int solutionnum = 0;
for(int i = 0; i < N; i++) {
coverage[i] = solve(i);
if(coverage[i] > maxcoverage) {
maxcoverage = coverage[i];
solutionnum = i;
}
if(coverage[i] == maxcoverage) {
if(num[i] < num[solutionnum]) {
maxcoverage = coverage[i];
solutionnum = i;
}
else if (num[i] == num[solutionnum]){
for(int j = num[i] - 1; j > 0; j--) {
if(denom[i][j] < denom[solutionnum][j]) {
maxcoverage = coverage[i];
solutionnum = i;
break;
}
if(denom[i][j] > denom[solutionnum][j]) break;
}
}
}
}
printf("max coverage =%4d :", maxcoverage);
for(int i = 0; i < num[solutionnum]; i++)
printf("%3d", denom[solutionnum][i]);
printf("\n");
}
}
Good Coalition
题目
The Dutch political system is in turmoil. There have been six coalition governments in the past fourteen years, all of which have fallen before completing their term in office. Recently there have been elections (again), the outcome of which has been described as “impossible” by several political commentators. The only bright spot in this bleak situation is that they have appointed you as the “informateur”. As the informateur it is your task to find a suitable coalition.
Being the rational person you are, you have decided the first negotiation attempt should be started between the parties forming the most stable coalition. A coalition is formed by a set of parties having won a strict majority of seats in the election (i.e. at least 76 seats out of a total of 150). The most stable coalition is one that has the highest chance of completing its term in office. A coalition falls (and new elections must be held) if a single party leaves the coalition. The probability of a coalition completing their term is estimated by the product of the probabilities of each party in the coalition completing their term. This probability is in turn based on historical data.
Find the best coalition and save the Netherlands from becoming a banana republic!
思路
01背包
用d[i]表示组成i人联盟的最大可能性。
应该注意的是同一个政党不能被多次选择，具体处理方式（两种）见代码
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
const int maxn = 150;
double dp[maxn + 1];
set<int> comb[maxn];
int n;
int s[maxn], p[maxn];
void solve() {
dp[0] = (double)1;
for(int i = 0; i < 76; i++) {
// printf("%lf ", dp[i]);
if(dp[i] == 0) continue;
for(int j = 0; j < n; j++) {
if(!comb[i].count(j)) {
if(dp[i + s[j]] < dp[i] * ((double)p[j] / 100.0)) {
dp[i + s[j]] = dp[i] * ((double)p[j] / 100.0);
set<int> newset(comb[i]);
newset.insert(j);
comb[i + s[j]] = newset;
// for(auto& setcontains: newset) cout << setcontains << ' ';
// cout << endl;
}
}
// dp[i + s[j]] = max(dp[i + s[j]], dp[i] * ((double)p[j] / 100.0));
}
}
}
void solve2() {
dp[0] = 1;
for(int i = 0; i < n; i++)
for(int j = maxn; j >= s[i]; j--)
// Process in reverse to avoid using party p more than once
// See if using party p is an improvement
dp[j] = max(dp[j], p[i] / 100.0 * dp[j - s[i]]);
}
int main() {
int kases;
scanf("%d", &kases);
for(int kase = 0; kase < kases; kase++) {
memset(dp, 0, sizeof(dp));
memset(s, 0, sizeof(s));
memset(p, 0, sizeof(p));
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d %d", &s[i], &p[i]);
solve2();
double maxposs = 0;
// for(int i = 76; i <= 150; i++)
// maxposs = max(maxposs, dp[i]);
for (int i = maxn; i > maxn/2; i--)
maxposs = max(maxposs, dp[i]);
printf("%.6lf\n", maxposs * 100.0);
}
return 0;
}