电源

3.19-3.25练习

2019-07-14 02:20发布

站内文章 / 电源技术
15488 0 1572
1. Uva11400 Lighting System Design: 有n种灯泡，不同种灯泡不能共用一个电源，且只能接在比额定低的电源上。给出每种灯泡的电压，电源费用，数量，单价，可以把一种灯泡换成额定更高的另一种灯泡来节约钱，求最优方案的费用。显然，每种电压的灯泡要么不换，要么全换。先将灯泡按照电压升序排序，令sum[i]为前i种灯泡的总数量，dp[i]为前i种灯泡的最小花费。状态转移方程为： dp[i]=min(dp[j]+(sum[i]-sum[j])*c[i]+k[i]),j；表示前j种灯泡用最优方案，第j+1个到第i个都用第i种灯泡。#include #include #include #include #include #include #include #include #include #include #include #include #define maxn 1005 #define INF 0x3f3f3f3f #define eps 1e-8 const int mod = 1e9 + 7; using namespace std; typedef long long ll; int n; int sum[maxn], dp[maxn]; struct node { int k; int val; int vol; int num; }e[maxn]; bool cmp(node a, node b) { return a.vol < b.vol; } int main() { while (scanf("%d", &n)) { if (n == 0)break; for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &e[i].vol, &e[i].k, &e[i].val, &e[i].num); sort(e + 1, e + n + 1, cmp); memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + e[i].num, dp[i] = INF; dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + (sum[i] - sum[j])*e[i].val + e[i].k); } printf("%d ", dp[n]); } return 0; }2. Uva11584 Partitioning by Palindromes: 给出一个小写字母组成的字符串，问最少能划分成多少个非空回文串。令dp[i]为前i个字符里最小的回文串个数，很容易想到dp[i]=min(dp[j]+1|j+1~i是回文串)。但这样操作的复杂度是O(n^3)。可以先以O(n^2)的复杂度预处理出i~j是否为回文串，这样在用上述方法进行处理的时候就可以将状态转移的时间从O(n)降为O(1)，总的复杂度为O(n^2)。#include #include #include #include #include #include #include #include #include #include #include #include #define maxn 1005 #define INF 0x3f3f3f3f #define eps 1e-8 const int mod = 1e9 + 7; using namespace std; typedef long long ll; int t, n, dp[maxn]; char s[maxn]; bool flag[maxn][maxn]; int main() { scanf("%d", &t); while (t--) { scanf("%s", s + 1); n = 0; for (int i = 1;; i++) { if (s[i] >= 'a'&&s[i] <= 'z')n++; else break; } memset(flag, 0, sizeof(flag)); for (int i = 1; i <= n; i++) { int l = i, j = 0; while (l + j <= n&&l - j > 0 && s[l + j] == s[l - j]) { flag[l - j][l + j] = 1; j++; } l = i, j = 0; while (l + j + 1 <= n&&l - j > 0 && s[l + j + 1] == s[l - j]) { flag[l - j][l + j + 1] = 1; j++; } } for (int i = 1; i <= n; i++)dp[i] = i; dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) if (flag[j + 1][i])dp[i] = min(dp[i], dp[j] + 1); } printf("%d ", dp[n]); } return 0; }3.Uva1625 ACM/ICPC Daejeon2011 Color Length: 给出两个长度为n和m的颜 {MOD}序列，要求按顺序合并成一个序列，定义每种颜 {MOD}的权值为最后出现的位置与首次出现的位置之差，求最小的序列权值。设dp[i][j]为两个数列分别移走i个和j个元素时，还需要多少权值。注意是“还需要多少”，因为本题需要最小化的量比较复杂，某种颜 {MOD}第一次出现时，并不知道什么时候会结束。而它最后一次出现时，也并不知道是什么时候开始的。如果记录每种颜 {MOD}第一次出现位置，状态会变得十分复杂，因此改进计算方法：并不是等到一种颜 {MOD}全部移完之后再计算，而是在中间逐步累加。当把一个颜 {MOD}移动到序列中时，所有“已经出现过但还没有结束”的颜 {MOD}的权值都需要加一，也就是说，我们只需要找出有多少颜 {MOD}已经开始且尚未结束，而不需要知道它们具体是哪些颜 {MOD}。因此，可以先预处理出每种颜 {MOD}在两个序列里初次和最终出现的位置，就可以在状态转移中以O(1)的复杂度计算出dp[i][j]中有多少种颜 {MOD}已经开始但尚未结束。状态转移方程dp[i][j]=min(dp[i+1][j],dp[i][j+1])+cnt[i][j]，总的时间复杂度为O(n*m)。#include #include #include #include #include #include #include #include #include #include #include #include #define maxn 5005 #define INF 0x3f3f3f3f #define eps 1e-8 const int mod = 1e9 + 7; using namespace std; typedef long long ll; int nn, n, m, st[26][2], en[26][2]; char s[maxn], t[maxn]; int dp[maxn][maxn], cnt[maxn][maxn]; int main() { scanf("%d", &nn); while (nn--) { scanf("%s%s", s + 1, t+ 1); n = strlen(s + 1); m = strlen(t + 1); for (int i = 0; i < 26; i++)st[i][0] = st[i][1] = INF, en[i][0] = en[i][1] = 0; for (int i = 1; i <= n; i++) { int u = s[i] - 'A'; if (st[u][0] == INF)st[u][0] = en[u][0] = i; if (en[u][0] != INF)en[u][0] = i; } for (int i = 1; i <= m; i++) { int u = t[i] - 'A'; if (st[u][1] == INF)st[u][1] = en[u][1] = i; if (en[u][1] != 0)en[u][1] = i; } for (int i = 1; i <= n + 1; i++) { for (int j = 1; j <= m + 1; j++) { int num = 0; for (int k = 0; k < 26; k++) { if (st[k][0] == INF&&st[k][1] == INF)continue; if (st[k][0] >= i&&st[k][1] >= j)continue; if (en[k][0] < i&&en[k][1] < j)continue; num++; } cnt[i][j] = num; } } dp[n + 1][m + 1] = 0; for (int i = n; i >= 1; i--)dp[i][m + 1] = dp[i + 1][m + 1] + cnt[i][m + 1]; for (int i = m; i >= 1; i--)dp[n + 1][i] = dp[n + 1][i + 1] + cnt[n + 1][i]; for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + cnt[i][j]; printf("%d ", dp[1][1]); } return 0; }4. 翻转括号：给出一个由括号组成的序列，问存在多少个这样的位置，使得只要翻转此处的括号就能使这个序列变成合法序列。将左括号'('视为+1，右括号')'视为-1则序列合法等价于所有前缀和非负且最后为零。求出前缀和后预处理左右的最小值，枚举翻转位置判断可行性即可。#include #include #include #include #include #include #include #include #include #include #include #include #define maxn 100050 #define INF 0x3f3f3f3f #define eps 1e-8 const int mod = 1e9 + 7; using namespace std; typedef long long ll; int t, n; char s[maxn]; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); scanf("%s", s); vectorv; stackst; for (int i = 0; i < n; i++) { if (s[i] == '(') st.push(i); else if (!st.empty()) st.pop(); else v.push_back(i); } while (!st.empty()) { int u = st.top(); v.push_back(u); st.pop(); } sort(v.begin(),v.end()); int ans = 0; if (v.size() == 2 && !(s[v[0]] == ')'&&s[v[1]] == '(')) { if (s[v[0]] == '(') { for (int i = v[1]; i < n; i++) { if (s[i] == '(') ans++; } } else { for (int i = v[0]; i >= 0; i--) { if (s[i] == ')') ans++; } } } printf("%d ", ans); } return 0; }



热门文章