DP专题(不定期更新)
2024-10-21 13:01:41
1、UVa 11584 Partitioning by Palindromes(字符串区间dp)
题意：给出一个字符串，划分为若干字串，保证每个字串都是回文串，同时划分数目最小。
思路：dp[i]表示以第i位结尾时最小的划分数目(初始均为0)
状态转移方程1：(初始均为0)当[j:i]是回文串（0≤j≤i，0≤i<n）:dp[i]=1(j==0);dp[i]=(dp[i]==0?dp[j-1]+1:min(dp[i],dp[j-1]+1))
状态转移方程2：(初始：dp[i]=i+1)当[j:i]是回文串（0≤j≤i，0≤i<n）:dp[i]=1(j==0);dp[i]=min(dp[i],dp[j-1]+1))
状态转移方程3：(初始：dp[i]=i+1(1≤i≤n);其他：dp[i]=0)当[j:i]是回文串（1≤j≤i，1≤i≤n）:dp[i]=min(dp[i],dp[j-1]+1))
#include<iostream>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn = ;
char s[maxn];
int dp[maxn];
int n;
bool Judge(int st, int ed)
{
for (; st <= ed; st++, ed--)
{
if (s[st] != s[ed]) return false;
}
return true;
}
int main()
{
cin >> n;
while (n--)
{
scanf("%s", s);
memset(dp, , sizeof(dp));
int sz = strlen(s);
for (int i = ; i < sz; i++)
{
for (int j = ; j <= i; j++)
{
if (Judge(j, i))
{
if (j == ) dp[i] = ;
else dp[i] = dp[i] == ? dp[j - ] + : min(dp[i], dp[j - ] + );
}
}
}
cout << dp[sz - ] << endl;
}
return ;
}
2、UVA 10534 Wavio Sequence(dp + LIS)
题意：给出一个字符串,求满足这样条件的子序列的最大长度：长度为奇数（假设为2*k+1），同时前k+1个严格递增，后k+1个严格递减。
思路：分别从左往右和从右往左分别算出以第i位结尾的最长递增子序列的长度L1、L2，然后得出以第i位为中点的满足条件的子序列的长度：min(L1,L2)*2-1（如果L1、L2包含该位），然后对每一位分别重复上述操作，得出最大长度。
#include<iostream>
#include<vector>
#include<memory.h>
#include<algorithm>
using namespace std;
const int maxn = ;
int maxl[maxn];
int maxr[maxn];
int p[maxn];
void exchange(int x, int pos, vector<int>&v, char c)
{
vector<int>::iterator it;
it = lower_bound(v.begin(), v.end(), x);
int p = it - v.begin();
v[p] = x;
if (c == 'l')maxl[pos] = p;
else maxr[pos] = p;
}
int main()
{
int n;
while (cin >> n)
{
vector<int>minlen;
for (int i = ; i < n; i++) cin >> p[i];
minlen.push_back(p[]);
maxl[] = ;
for (int i = ; i < n; i++)
{
if (p[i] > minlen.back())
{
maxl[i] = minlen.size();
minlen.push_back(p[i]);
}
else
{
exchange(p[i], i, minlen, 'l');
}
}
minlen.clear();
minlen.push_back(p[n - ]);
maxr[n - ] = ;
for (int i = n - ; i >= ; i--)
{
if (p[i] > minlen.back())
{
maxr[i] = minlen.size();
minlen.push_back(p[i]);
}
else
{
exchange(p[i], i, minlen, 'r');
}
}
int len = ;
for (int i = ; i < n; i++)
{
int tmp = min(maxl[i], maxr[i]) * + ;
if (tmp > len) len = tmp;
}
cout << len << endl;
}
return ;
}
3、uva 11404 - Palindromic Subsequence(dp)
题意：给出一个字符串，求其最长回文子串，并输出该字串。如果有多个，输出字典序最小的那个。
思路：如果只求长度：dp[i][j]=dp[i+1][j-1]+2(s[i]==s[j]);dp[i][j]=max(dp[i+1][j],dp[i][j-1])(s[i]!=s[j])
在此基础上可以用string来保存临时回文子串。
#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
const int maxn = ;
struct node
{
int len;
string str;
}dp[maxn][maxn]; int main()
{
string s;
while (cin >> s)
{
int len = s.length();
memset(dp, , sizeof(dp));
for (int i = ; i < len; i++)
{
dp[i][i].len = ;
dp[i][i].str = s[i];
}
for (int i = len - ; i >= ; i--)
{
for (int j = i; j < len; j++)
{ if (s[i] == s[j])
{
if (i == j)
{
dp[i][j].len = ;
dp[i][j].str = s[i];
}
else
{
dp[i][j].len = dp[i + ][j - ].len + ;
dp[i][j].str = s[i] + dp[i + ][j - ].str + s[j];
}
}
else
{
if (dp[i + ][j].len > dp[i][j - ].len)
{
dp[i][j].len = dp[i + ][j].len;
dp[i][j].str = dp[i + ][j].str;
}
else if (dp[i + ][j].len < dp[i][j - ].len)
{
dp[i][j].len = dp[i][j - ].len;
dp[i][j].str = dp[i][j - ].str;
}
else
{
dp[i][j].len = dp[i][j - ].len;
if (dp[i][j - ].str < dp[i + ][j].str) dp[i][j].str = dp[i][j - ].str;
else dp[i][j].str = dp[i + ][j].str;
}
}
}
}
cout << dp[][len - ].str << endl;
}
return ;
}
4、UVA 11795 - Mega Man's Mission(状态压缩dp)
题意：洛克人手里有一把武器，能够杀死部分特定敌人（可以杀死的记为1，无法杀死的记为0），同时，他杀死敌人后，能够使用被杀死的敌人的武器，其武器同样也只能杀死特定的敌人。求能杀死所有敌人的方案数。
思路：对于n个敌人，共有2^n-1种状态（用一个int即可表示），可以先求出每种状态下能够杀死的敌人atk[i]（即该状态i下杀死的敌人的武器被获得后能够杀死的敌人），之后，对于i这种状态，如果该状态下能够杀死敌人j,如果i^(1<<j)这种状态(不能杀死j)下能够杀死j(atk[i^(1<<j)]&1<<j),则dp[i]+=dp[i^(1<<j)]。
#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
typedef long long ll;
char s[];
const int maxn = ( << ) + ;
int N;
int w[maxn];//存储洛克人[0]和敌人[1:]的武器
int atk[maxn];//用来保存每个状态可以杀死的机器人
ll dp[maxn];// 2 的 16 次方会爆 int。 // 用来统计每种状态的顺序方案种数
int Exchange()
{
int ans = ;
int sz = strlen(s);
for (int i = ; i < sz; i++)
{
if (s[i] == '') ans = ans | ( << i);//第i+1位如果能被杀掉，则第i+1位为1
}
return ans;
}
int main()
{
int T;
cin >> T;
int Case = ;
while (T--)
{
cin >> N;
for (int i = ; i <= N; i++)
{
scanf("%s", s);
w[i] = Exchange();
//cout << i << ' ' << w[i] << endl;
}
int total = ( << N) - ;//对于N个敌人，一共最多有2^N-1种状态（每个敌人能够杀死或不能杀死）
for (int st = ; st <= total; st++)
{//st即为二进制存储的状态
atk[st] = w[];//初始为洛克人所拿的武器能够杀死的人
for (int i = ; i <= N; i++)//对于每个敌人
{
int j = i - ;//i其在所存二进制里的位置
if (st&( << j))
{//如果该状态可以杀死 i，那么该状态也可以杀死i所能干掉的
atk[st] = atk[st] | w[i];
}
}
}
memset(dp, , sizeof(dp));
dp[] = ;//一个都不杀死的方案数为1
for (int st = ; st <= total; st++)
{
for (int i = ; i < N; i++)
{//对于N个敌人
if (st & << i)
{//如果该状态能够杀死第i+1个敌人(敌人从1开始编号，但是在二进制存储的杀死状态中存储的位置为i),那么 st 由不能杀死 i 的状态转移过来, 即st^(1<<i)（异或）
if (atk[st ^ ( << i)] & << i)//并且st^(1<<i)这种状态能够杀死该敌人
{
dp[st] += dp[st ^ ( << i)];
}
}
}
}
printf("Case %d: %lld\n", Case++, dp[total]);
}
return ;
}
5、UVA 10564 Paths through the Hourglass(dp)
题意：有一个漏斗形的图，从某一行只能向左下或右下走，走过的路径上的点数之和要等于S。求路径数，若存在，则输出从第一行最左侧开始，同时所走方向形成的字典序最小的字符串。（由‘L’、‘R’组成）。
思路：从下往上dp,dp[i][j][k] 代表从(i, j)点往下走到最后一层和为k的方案数,那么，显然可以得到状态转移：
dp[i][j][k] = dp[i + 1][left][k - val] + dp[i + 1][right][k - val], val = (i, j)格上的数字，left是往坐下走的坐标，right往右下走的坐标
#include<iostream>
#include<memory.h>
#include<cstdio>
using namespace std;
typedef long long ll;
int N, S;
ll dp[][][];
int m[][];
void Input()
{
for (int i = ; i <= N; i++)
{
for (int j = ; j <= N - i+; j++)
{
scanf("%d", &m[i][j]);
}
}
for (int i = N+; i <= * N - ; i++)
{
for (int j = ; j <= i - N + ; j++)
{
scanf("%d", &m[i][j]);
}
}
}
void Print()
{
int pos;
for (int i = ; i <= N; i++)
{
if (dp[][i][S])
{
cout <<i-<< ' ';
pos = i;
break;
}
}
int sum = S;
for (int i = ; i <= N; i++)
{
if (dp[i][pos - ][sum - m[i - ][pos]])
{
cout << 'L';
sum -= m[i - ][pos];
pos--;
}
else
{
cout << 'R';
sum -= m[i - ][pos];
}
}
for (int j = N+; j <= * N - ; j++)
{
if (dp[j][pos][sum - m[j - ][pos]])
{
cout << 'L';
sum -= m[j - ][pos];
}
else
{
cout << 'R';
sum -= m[j - ][pos];
pos++;
}
}
cout << endl;
} int main()
{
while (cin >> N >> S, N != || S != )
{
Input();
memset(dp, , sizeof(dp));
for (int i = ; i <= N; i++) dp[ * N - ][i][m[ * N - ][i]] = ;
for (int i = * N - ; i >= N; i--)
{
for (int j = ; j <= i - N + ; j++)
{
int v = m[i][j];
for (int tv = v; tv <= S; tv++)
{
dp[i][j][tv] = dp[i + ][j][tv-v] + dp[i + ][j + ][tv-v];
}
}
}
for (int i = N - ; i >= ; i--)
{
for (int j = ; j <= N - i+; j++)
{
int v = m[i][j];
for (int tv = v; tv <= S; tv++)
{
dp[i][j][tv] = dp[i + ][j][tv-v] + dp[i + ][j - ][tv-v];
}
}
}
ll ans = ;
for (int i = ; i <= N; i++) ans += dp[][i][S];
if (ans == ) cout << ans << endl << endl;
else
{
printf("%lld\n", ans);
Print();
}
}
return ;
}
6、UVA 11552 Fewest Flops
题意：给出一个长度能够整除k的字符串，整除后得到的子串中的字符看可以重新组合。求最后得到的新的字符串中满足该条件（字串中每个字符都相同）的子串的最小数目。例如：“abccd”中，这样的数目有4个：“a”,"b","cc","d".
思路：DP[i][j]表示前i段，第i段以第j个字符结尾时最小的满足条件的字串数目。
DP[i][j] = min(DP[i][j],DP[i - 1][l] + cnt - 1)(i-1段以第l个字符结尾时，该字符和第i段第一个字符相同时)
DP[i][j] = min(DP[i][j],DP[i - 1][l] + cnt)(i-1段以第l个字符结尾时，该字符和第i段第一个字符不同时)
#include<map>
#include<string>
#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
#define maxn 1020
int dp[maxn][maxn];
int main()
{
int n;
cin >> n;
while (n--)
{
int k;
cin >> k;
string s;
cin >> s;
int l = s.length();
int tl = l / k;
map<char, int>m;
int count = ;
memset(dp, , sizeof(dp));
for (int i = ; i < k; i++)
{
if (!m[s[i]])
{
m[s[i]] = ;
count++;
}
}
for (int i = ; i < k; i++) dp[][i] = count;
for (int j = ; j<tl; j++)
{
m.clear();
count = ;
for (int i = ; i < k; i++)
{
if (!m[s[i + j*k]])
{
m[s[i + j*k]] = ;
count++;
}
}
for (int i = ; i < k; i++) dp[j][i] = l;
for (int i = ; i < k; i++)
{
for (int l = ; l < k; l++)
{
if (m[s[l + (j - )*k]] && (count == || s[l + (j - )*k] != s[i + j*k]))
{//如果j-1段中第l个字母在第j段中出现过，并且第j段中字母种类只有一种或者有多种但最后一个字母不是它
dp[j][i] = min(dp[j][i], dp[j - ][l] + count - );
}
else dp[j][i] = min(dp[j][i], dp[j - ][l] + count);
}
}
}
int mincount = l;
for (int i = ; i < k; i++) mincount = min(mincount, dp[tl - ][i]);
cout << mincount << endl;
}
return ;
}
7、UVa 11825 Hackers’ Crackdown
题意：有一个分布式网络，每台电脑都有若干台和它相邻，同时所有电脑都有N种服务运行。现在有个黑客，他想要发送病毒，一台电脑只能植入一种病毒，只有所有电脑都瘫坏才能瘫坏掉一种服务，求其能够干掉的最多的服务种数。
思路：2进制状态压缩保存每台电脑的邻接状态，并用2进制来保存每种状态下能攻陷的电脑。dp[i]表示i状态下能干掉的最多的服务数目。dp[i] = max(dp[i], dp[i^j] + 1)。详细见注释
//状压DP
#include<iostream>
#include<algorithm>
using namespace std;
const int maxst = ( << );
int ini[];
int cover[maxst];
int dp[maxst];
int main()
{
int n;
int Case = ;
while (~scanf("%d", &n))
{
if (n == ) break;
for (int i = ; i < n; i++)
{
ini[i] = |(<<i);//包括自身
int m;
scanf("%d", &m);
for (int j = ; j < m; j++)
{
int k;
scanf("%d", &k);
ini[i] |= ( << k);//加上邻居
}
}
int total = ( << n) - ;//总状态数
for (int i = ; i <=total; i++)
{
cover[i] = ;
for (int j = ; j < n; j++)
{
if (i&( << j))//如果该状态能够瘫坏第j台电脑
{
cover[i] |= ini[j];//那么也能瘫坏其邻接的电脑
}
}
}
dp[] = ;
for (int i = ; i <= total; i++)
{
dp[i] = ;
//枚举子集
for (int j = i; j > ; j = (j - )&i)
{
if (cover[j] == total)//如果子集的状态下能够干掉所有的电脑
{
dp[i] = max(dp[i], dp[i^j] + );//那么该状态的能够关闭的服务为max{该状态下能最多关闭的服务数,该状态i和能够干掉所有的电脑的子集的补集所能能关闭的方案数+1（这个1由该子集j提供）}
}
}
}
printf("Case %d: %d\n",Case, dp[total]);
Case++;
}
return ;
}
8、UVA-10635 Prince and Princess
题意：求两个序列的公共最长子序列。
思路：听说最长公共子序列算法会超时……由于序列每个数都不同，可以转换为求b的最长递增子序列，只需将a数组按顺序从1开始重新编号，建立映射。
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int maxl = * ;
int numa[maxl];
int numb[maxl];
map<int, int>m;
void exchange(int x, vector<int>&v)
{
vector<int>::iterator it;
it = lower_bound(v.begin(), v.end(), x);
int p = it - v.begin();
v[p] = x;
} int main()
{
int t;
int Case = ;
scanf("%d", &t);
while (t--)
{
int n, p, q;
scanf("%d%d%d", &n, &p, &q);
for (int i = ; i < p+; i++)
{
scanf("%d", &numa[i]);
m[numa[i]] = i + ;
}
for (int i = ; i < q+; i++)
{
scanf("%d", &numb[i]);
if (m[numb[i]]) numb[i] = m[numb[i]];
else numb[i] = ;
}
vector<int>minlen;
minlen.push_back(numb[]);
for (int i = ; i < q+; i++)
{
if (numb[i] > minlen.back()) minlen.push_back(numb[i]);
else
{
exchange(numb[i], minlen);
}
}
printf("Case %d: %d\n",Case, minlen.size());
Case++;
}
return ;
}
9、Uva-10891-Game of Sum
题意：A和B两个人，每次可以轮流从一个数组的左端或右端开始拿走若干个数字，直到数组为空，A先手。求最优选择下A能比B最多高出多少。
思路：DP，dp[st][ed] = sum[ed] - sum[st - 1] - min(0,L[st][ed - 1],R[st + 1][ed]),L[st][ed] = min(L[st][ed - 1], dp[st][ed]);R[st][ed] = min(R[st + 1][ed], dp[st][ed]).
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = ;
int n;
//const int maxV=12;
int a[maxn + ];
int dp[maxn + ][maxn + ];
int L[maxn + ][maxn + ], R[maxn + ][maxn + ];
int sum[maxn + ];
int main()
{
while (~scanf("%d", &n) && n)
{
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
sum[] = ;
for (int i = ; i <= n; i++)
{
dp[i][i] = a[i];//dp[st][ed]表示[st,ed]区间，先手最多得分。
sum[i] = sum[i - ] + a[i];//L[st,ed]=min{dp[st][k] } ;(st<=k<=ed)
L[i][i] = R[i][i] = dp[i][i];//R[st,ed]=min{dp[k][ed]};(st<=k<=ed)
}
for (int add = ; add<n; add++)
{
for (int st = ; st + add <= n; st++)
{
int ed = st + add;
int m = ; //m表示此阶段的后手最少能拿多少
m = min(m, L[st][ed - ]);//表示从右边拿起
m = min(m, R[st + ][ed]);//表示从左边拿起
dp[st][ed] = sum[ed] - sum[st - ] - m;
L[st][ed] = min(L[st][ed - ], dp[st][ed]);
R[st][ed] = min(R[st + ][ed], dp[st][ed]);
}
}
printf("%d\n", dp[][n] - (sum[n] - sum[] - dp[][n]));
}
return ;
}
10、Uva 10859 - Placing Lampposts
题意：在一张图中，选择结点放置路灯，路灯会照亮连接该结点的路径，问使所有路径都能被照到的最小路灯数目为多少？同时在所有最小的方案中，要保证至少被两盏灯照亮的道路最多。
思路：树形DP。优化：x=M*v1+v2，其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。v1表示放置的路灯数目尽可能小，v2表示被一盏灯照亮的路尽可能小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)。每放一盏灯 + 2000(m)（因为边的最大数量为1000），每增加1条照亮一次的边 + 1.
①节点i处不放街灯，那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 }，如果i不是根节点，那么结果+1，因为i和父亲连接的这条边只被一盏灯照亮。
②节点i处放街灯，dp(i, j) = sum{ dp(v,1) | v取遍i的所有儿子节点 } +M，如果i不是根节点而且j = 0，那么结果 + 1。
//树形DP
//f(i,j)表示第i盏灯的父亲是否点亮所以j=0|1如果父亲放了，那么自己放或者不放都可以那么f(i,j)=max{∑f(ison,0)∑f(ison,1)}，如果父亲没有放置，那么自己必须放那么f(i,0)=∑f(ison,1)但是这个时候要让被灯照亮两次的边尽量多，那么应该让被照亮一次的边尽量的少，那么另m=n×x+yx代表覆盖当前的子树的灯的数量，y代表当前子树中覆盖完成的最少的被照亮一次的边的数量前提是让y的最大值小于n那么这样x就成为了首要重要的权值，y是次要的然后dp方程改一下 //f(i, 0) = (∑f(ison, 1)) + 1
//加1是因为自己和自己的父亲又有一条边被照亮一次所以加1，
//f(i, 1) = max{ (∑f(ison,0)) + 1,∑f(ison,1) }
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define NODENUM 1005
#define EDGENUM 1005
#define MAXN 1005
using namespace std;
//优化x=M*v1+v2，其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。v1表示放置的路灯数目尽可能小，v2表示被一盏灯照亮的路尽可能小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)
int root;
const int m = ;//即理论的M struct EdgeNode
{
int to, next;
} E[ * EDGENUM];
int edgenum, head[NODENUM], N, T, M;
bool vis[NODENUM];
int ans;
int dp[NODENUM][];//[0]表示不放灯，[1]表示放灯 void init()
{
edgenum = ;//路条数为0
memset(head, -, sizeof(head));
memset(vis, , sizeof(vis));
ans = ;
} void add(int x, int y)
{
edgenum++;
E[edgenum].next = head[x];
head[x] = edgenum;
E[edgenum].to = y;
} void dfs(int s)
{
vis[s] = ;
int sum0 = , sum1 = ; for (int p = head[s]; p != -; p = E[p].next)
{
int v = E[p].to;
if (!vis[v])
{
dfs(v);
sum0 += dp[v][];
sum1 += dp[v][];
}
}
if (s == root) dp[s][] = min(sum1 + m, sum0), ans += dp[s][];
else dp[s][] = min(sum0 + , sum1 + m), dp[s][] = sum1 + m + ;
}
//每放一盏灯 + 2000(m)（因为边的最大数量为1000），每增加1条照亮一次的边 + 1.
//决策一：节点i处不放街灯，那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 }，如果i不是根节点，那么结果+1，因为i和父亲连接的这条边只被一盏灯照亮。
//决策二：节点i处放街灯，dp(i, j) = sum{ dp(v,1) | v取遍i的所有儿子节点 } +M，如果i不是根节点而且j = 0，那么结果 + 1。
void build()
{
scanf("%d%d", &N, &M);
for (int i = ; i<M; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);//无向边
add(b, a);
}
} int main()
{
scanf("%d", &T);//测试用例
while (T--)
{
init();
build();
for (int i = ; i<N; ++i) if (!vis[i]) dfs(root = i);//可能有多颗树
printf("%d %d %d\n", ans / m, M - ans%m, ans%m);
}
return ;
}
11、uva 10817 Headmaster's Headache ( 状态压缩dp+sstream应用)
题意：学校现在招老师，给出原来任职的老师和前来应聘的老师的信息，求在保证每门科目至少有两个老师教的情况下，最小花费是多少。
思路：把学科的信息用二进制状态压缩，s1对应还需要一个老师教的科目,s2对应已经足够老师教的科目.状态设为dp[i][s1][s2]：代表到第i个老师为止，校长最少需要花多少钱达到目标。当i < m 时，我们必须选择，状态只能更新为添加老师，当i >= m时， 就可以更新为选或不选老师两种状态。s1：当某个学科还需要1个老师教时，该位记为1，否则记为0；s2:当某个学科已经有足够的老师教时，该位记为1，否则记为0。
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
const int INF = 0x7f7f7f7f, MAXN = ;
int s, m, n, teach[MAXN], cost[MAXN], dp[MAXN][ << ][ << ]; int DP(int i, int s1, int s2)//s1对应还需要一个老师教的科目,s2对应已经足够老师教的科目.状态设为dp[i][s1][s2]：代表到第i个老师为止，校长最少需要花多少钱达到目标。当i < m 时，我们必须选择，状态只能更新为添加老师，当i >= m时， 就可以更新为选或不选老师两种状态。
//s1,s2均为2进制数，每一位表示该课程有无老师
//s1：当某个学科还需要1个老师教时，该位记为1，否则记为0
//s2:当某个学科已经有足够的老师教时，该位记为1，否则记为0
{
if (i == m + n) return s2 == ( << s) - ? : INF; //每个科目都至少两个老师了，那么就不需要再花钱了
int &ret = dp[i][s1][s2];//引用
if (ret >= ) return ret;
ret = INF;
if (i >= m) ret = DP(i + , s1, s2); //不选
s2 |= (s1 & teach[i]); //老师能教，并且差一个老师，那么一并运算，剩下的就是满足条件的科目
s1 |= teach[i]; //或上去，没人教的科目肯定变成差一个人教
ret = min(ret, cost[i] + DP(i + , s1, s2)); //选
return ret;
} int main()
{
while (~scanf("%d%d%d",&s,&m,&n))
{
if (s == )break;
cin.get();
string ss;
int x;
for (int i = ; i < m + n; ++i)
{
getline(cin, ss);
stringstream sss(ss);
sss >> cost[i];
teach[i] = ;
while (sss >> x)
{
teach[i] |= << (x - );
}
}
memset(dp, -, sizeof dp);
//for (int i = 0; i < m + n; ++i) cout << cost[i] << ':' << teach[i] << endl;
cout << DP(, , ) << '\n';
}
return ;
}
12、hdu 1024 Max Sum Plus Plus
题意：给n个数，现在需要找到m个区间，使得每个区间内元素的和累加起来最大。
思路：dp[i][j]表示前j个数在选取第j个数的前提下分成i段的最大值。dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);dp[i][j-1]+num[j]表示前j-1个分成i组，j放在其他组里；max(dp[i-1][k]|(0<k<j))+num[j]表示前k个分成i-1组的最大值加上第j个独立成组的大小。
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
const int maxn = ;
const int INF = 0x7fffffff; int num[maxn];
int dp_now[maxn];
int max_pre[maxn];
//dp[i][j]表示前j个数在选取第j个数的前提下分成i段的最大值。
//dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);
//dp[i][j-1]+num[j]表示前j-1个分成i组，j放在其他组里
//max(dp[i-1][k]|(0<k<j))+num[j]表示前k个分成i-1组的最大值加上第j个独立成组的大小
int main()
{
while (~scanf("%d%d", &m, &n))
{
for (int i = ; i <= n; i++) scanf("%d", &num[i]);
memset(dp_now, , sizeof(dp_now));
memset(max_pre, , sizeof(max_pre));
int tmax;
for (int i = ; i <= m; i++)
{
tmax = -INF;
for (int j = i; j <= n; j++)
{
dp_now[j] = max(dp_now[j - ]+num[j], max_pre[j - ] + num[j]);
max_pre[j - ] = tmax;
tmax = max(tmax, dp_now[j]);
}
}
printf("%d\n", tmax);
}
return ;
}
13、hdu 1029 Ignatius and the Princess IV
题意：给出n个数（n为奇数），输出n个数中至少出现（n+1）/2的数。
思路：扫描一边数组即可。
#include<iostream>
using namespace std;
int main()
{
int n;
while (~scanf("%d", &n))
{
int cal = ;
int m;
int t;
while (n--)
{
scanf("%d", &t);
if (cal == )
{
m = t;
cal++;
}
else
{
if(t != m)
{
cal--;
}
else cal++;
}
}
printf("%d\n", m);
} return ;
}
14、hdu 1069 Monkey and Banana
题意：给出若干种类型的的砖块，其底面的长宽可由任意两边确定。现在把这些砖块叠放，砖块上方的砖块的底面的长和宽都必须小于该砖块的长与宽，求最大高度。
思路：先得到各种砖块各种摆放的方式，然后按底面长和宽从大到小排序。从小的开始dp，如果当前块的长和宽比之前的要大，则累加。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
struct node
{
int l;
int w;
int h;
}blocks[maxn*];
int dp[maxn * ];//以i为底的最高高度
bool Cmp(const node&a, const node&b)
{
if (a.l == b.l)return a.w > b.w;
else return a.l > b.l;
}
int main()
{
int n;
int Case = ;
while (~scanf("%d", &n))
{
if (n == )break;
int cnt = ;
while (n--)
{
int xi, yi, zi;
scanf("%d%d%d", &xi, &yi, &zi);
blocks[cnt].l = xi, blocks[cnt].w = yi, blocks[cnt].h = zi;
cnt++;
blocks[cnt].l = yi, blocks[cnt].w = xi, blocks[cnt].h = zi;
cnt++;
blocks[cnt].l = xi, blocks[cnt].w = zi, blocks[cnt].h = yi;
cnt++;
blocks[cnt].l = zi, blocks[cnt].w = xi, blocks[cnt].h = yi;
cnt++;
blocks[cnt].l = yi, blocks[cnt].w = zi, blocks[cnt].h = xi;
cnt++;
blocks[cnt].l = zi, blocks[cnt].w = yi, blocks[cnt].h = xi;
cnt++;
}
sort(blocks, blocks + cnt, Cmp);
for (int i = ; i < cnt; i++) dp[i] = blocks[i].h;
for (int i = cnt - ; i >= ; --i)
{//从小的开始DP
for (int j = i + ; j < cnt; j++)
{
if (blocks[j].l < blocks[i].l&&blocks[j].w < blocks[i].w)
{
if (dp[j] + blocks[i].h > dp[i])
{
dp[i] = dp[j] + blocks[i].h;
}
}
}
}
int ans = ;
for (int i = ; i < cnt; i++)
{
ans = max(ans, dp[i]);
}
printf("Case %d: maximum height = %d\n", Case++, ans);
} return ;
}
15、hdu 1074 Doing Homework
题意：每门功课的作业都有自己的截止日期和做完所需时间。同时，每门功课都有自己学分，如果不能在截止日期前上交作业，每拖一天则多扣一个学分。问最少会扣多少学分。
思路：科目最多有15门，枚举每门的完成状态，从小到大枚举，如果当前状态st下,需要完成某项作业j，则考虑其不需完成该作业的状态stt=st^(1<<j),如果加上这门课后其所扣学分更少，则更新，并记录前驱，以便后续输出。
#include<iostream>
#include<stack>
#include<cstdio>
#include<memory.h>
using namespace std;
int n;
const int maxn = ;
const int INF = 0x7fffffff;
struct sbj
{
char nm[];//科目名称
int deadline;//截止日期
int cost;//完成需花费的时间
}homework[maxn];
struct node
{
int tm;
int score;
int pre;
int now;
}dp[ << maxn];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
{
int total = ( << n) - ;
for (int i = ; i < n; i++)
{
scanf("%s%d%d", homework[i].nm, &homework[i].deadline, &homework[i].cost);
}
memset(dp, , sizeof(dp));
for (int st = ; st <= total; st++)
{//从小的枚举
dp[st].score = INF;
for (int j = n - ; j >= ; j--)
{//从最后往前枚举
if (st&( << j))
{
int st2 = st ^ ( << j);
int t = dp[st2].tm + homework[j].cost - homework[j].deadline;
if (t < ) t = ;
if (t + dp[st2].score < dp[st].score)
{
dp[st].score = t + dp[st2].score;
dp[st].pre = st2;
dp[st].now = j;
dp[st].tm = dp[st2].tm + homework[j].cost;
}
}
}
}
printf("%d\n", dp[total].score);
int pre = total;
stack<int>s;
while (pre)
{
s.push(dp[pre].now);
pre = dp[pre].pre;
}
while (!s.empty())
{
printf("%s\n", homework[s.top()].nm);
s.pop();
}
}
}
return ;
}
16、hdu 1087 Super Jumping! Jumping! Jumping!
题意：现在需要从起点到终点踩格子，每次只能向前踩比当前各自大的数字的格子，求所踩格子的数字之和的最大值。
思路：dp[i]代表以第i个数结尾的最大上升子序列的和，对于当前的格子i，遍历之前的dp[j]（0<=j<=i）,如果dp[j]+num[i]>dp[i],则更新dp[i]的值。
#include<iostream>
using namespace std;
const int maxn = ;
int num[maxn];
int dp[maxn];//dp[i]代表以第i个数结尾的最大上升子序列的和
int main()
{
int n;
while (~scanf("%d", &n))
{
if (n == ) break;
for (int i = ; i < n; i++) scanf("%d", &num[i]);
memset(dp, , sizeof(dp));
dp[] = num[];
int ans = dp[];
for (int i = ; i < n; i++)
{
dp[i] = num[i];
for (int j = ; j <= i; j++)
{
if (num[j] < num[i])
{
if (dp[j] + num[i] > dp[i])
{
dp[i] = dp[j] + num[i];
}
}
}
if (dp[i] > ans) ans = dp[i];
}
printf("%d\n", ans);
}
return ;
}
17、hdu 1114 Piggy-Bank
题意：给出空的储钱罐的重量和当前储钱罐的重量，给出n种硬币的重量和面值。求使得储钱罐内的最小的硬币总价值。
思路：dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);dp[i]表示硬币总重量为i时，储钱罐内硬币的最低价值。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
const int maxw = ;
const int maxp = ;
const int INF = 0x7fffffff; int dp[maxw];
struct coin
{
int p;
int w;
}coins[maxn];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int e, f;
scanf("%d%d", &e, &f);
int totalw = f - e;//装硬币的重量
int minwight = maxw;
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
{
scanf("%d%d", &coins[i].p, &coins[i].w);
if (coins[i].w < minwight) minwight = coins[i].w;
}
if (minwight > totalw)
{
printf("This is impossible.\n");
continue;
}
for (int i = ; i <= totalw; i++) dp[i] = INF;
dp[] = ;
for (int i = ; i < n; i++)
{
for (int v = ; v <= totalw; v++)
{
if (v - coins[i].w >= && dp[v - coins[i].w]!=INF)
{
/*if(dp[v]>=0)dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
else dp[v] = dp[v - coins[i].w] + coins[i].p;*/
dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
}
}
}
if(dp[totalw]<INF)printf("The minimum amount of money in the piggy-bank is %d.\n", dp[totalw]);
else
{
printf("This is impossible.\n");
}
}
return ;
}
18、HDU 1176 免费馅饼
题意：天上开始掉馅饼，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。刚开始时站在5的位置，问最后最多能接住多少馅饼。
思路：从最大时间往前DP。
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<algorithm>
using namespace std;
int n;
const int maxn = ;
const int maxt = ;
const int INF = 0x7fffffff;
int dp[maxt][];
int main()
{
while (~scanf("%d", &n))
{
if (n == )break;
memset(dp,, sizeof(dp));
int maxtt = ;
for (int i = ; i < n; i++)
{
int x, t;
scanf("%d%d", &x, &t);
dp[t][x]++;
if (t > maxtt) maxtt=t;
}
for (int i = maxtt-; i >= ; i--)
{
for (int st = ; st <= ; st++)
{
if (st == ) dp[i][st] += max(dp[i + ][st], dp[i + ][st + ]);
else if(st==)dp[i][st] += max(dp[i + ][st], dp[i + ][st - ]);
else dp[i][st] += max(dp[i + ][st - ], max(dp[i + ][st], dp[i + ][st + ]));
}
}
printf("%d\n", dp[][]);
}
return ;
}
最新文章
- WebGIS中等值面展示的相关方案简析
- 启动eclipse时：java is started but returned code 13
- Leetcode: Bomb Enemy
- redis windows下的环境搭建
- SQL Server集群服务器的优缺点
- Windows上的的神技能，你知道几个？（Windows技巧大全，已更新）
- Windows系统下Oracle数据库冷备
- Covariance and Contravariance in C#, Part Two: Array Covariance
- 使用js在网页上记录鼠标划圈的小程序
- selenium webdriver 使用Chrome 浏览器
- 为多态基类声明virtual析构函数
- 服务端预渲染之Nuxt(介绍篇)
- 常见的cmake工程做法
- 记一次node进程无法kill 问题
- [转]Eclipse快捷键 10个最有用的快捷键
- Factorial Problem in Base K（zoj3621）
- SCIKIT-LEARN与GBDT使用案例
- SQL字符串分割转列，Sql列转字符串
- showDoc项目文档管理工具
- [JSON].connectionValue()