1013 Battle Over Cities
原来的图不一定连通，所以dfs统计连通块的时候要遍历所有的点。
pta总是有一些奇怪的边缘数据，
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
vector<int> G[maxn];
int n, m, k;
int del[maxn];
bool vis[maxn];
int ans[maxn];
int no;
void dfs(int u, int p){
vis[u] = true;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(v == p || v==no||vis[v]) continue;
dfs(v, u);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>k;
int u, v;
for(int i=1; i<=m; i++){
cin>>u>>v;
G[u].push_back(v), G[v].push_back(u);
}
for(int i=1; i<=k; i++){
cin>>del[i];
int tot = 0;
no = del[i];
cls(vis, 0);
for(int j=1; j<=n; j++){
if(j == del[i]) continue;
if(!vis[j]){
tot++;
dfs(j, -1);
}
}
ans[i] = tot-1;
}
for(int i=1; i<=k; i++) cout<<ans[i]<<endl;
return 0;
}
unidirectional TSP
记录移动状态的dp问题，还算比较的常规
求一条路径最短的矩阵路径，若权重相同则要使行序的字典序最小。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int num[15][105];
int dp[15][105];
int nex[15][105];
int n, m;
int main(){
ios::sync_with_stdio(false);
while(~scanf("%d%d", &n, &m)){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf("%d", &num[i][j]);
dp[i][j] = inf;
}
}
int ans = inf;
for(int col=m; col>=1; col--){
for(int row=1; row<=n; row++){
if(col == m) dp[row][col] = num[row][col];
else{
int to[3] = {row-1, row, row+1};
if(row == n) to[2] = 1;
if(row==1) to[0] = n;
sort(to, to+3);
for(int j=0; j<3; j++){
int temp = dp[to[j]][col+1]+num[row][col];
if(temp<dp[row][col]){
dp[row][col] = temp;
nex[row][col] = to[j];
}
}
}
}
}
int mi = inf;
int first = -1;
for(int i=1; i<=n; i++){
if(dp[i][1]<mi){
mi = dp[i][1];
first = i;
}
}
int j=1;
for(int i=first; j<=m; j++){
printf("%d%c", i, j==m?'
':' ');
i = nex[i][j];
}
printf("%d
", mi);
}
return 0;
}
The lightning system
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
struct Node{
int v, k, c, l;
bool operator < (const Node &b) const{
return v<b.v;
}
}node[maxn];
int n;
int dp[maxn];
int pre[maxn];
int main(){
ios::sync_with_stdio(false);
while(cin>>n&&n){
for(int i=1; i<=n; i++){
cin>>node[i].v>>node[i].k>>node[i].c>>node[i].l;
//pre[i] = pre[i-1]+node[i].l;
}
sort(node+1, node+1+n);
pre[0] = 0;
for(int i=1; i<=n; i++) dp[i] = inf, pre[i] = pre[i-1]+node[i].l;
dp[1] = node[1].l*node[1].c+node[1].k;
dp[0] = 0;
for(int i=2; i<=n; i++){
for(int j=0; j<i; j++){
dp[i] = min(dp[i], dp[j]+(pre[i]-pre[j])*node[i].c+node[i].k);
}
}
cout<<dp[n]<<endl;
}
return 0;
}
jin ge jin qu(01背包)
条件有点唬人导致不敢做背包
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 180*50+678+10;
int dp[maxn];
int n;
int a[55];
int remain;
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
int kase = 1;
while(_--){
cin>>n>>remain;
int tot = 0;
for(int i=1; i<=n; i++) cin>>a[i], tot+=a[i];
for(int i=1; i<=remain; i++) dp[i] = -1;
dp[0] = 0;
for(int i=1; i<=n; i++){
for(int v=remain-1; v>=a[i]; v--){
if(dp[v-a[i]]>=0){
dp[v] = max(dp[v], dp[v-a[i]]+1);
}
}
}
int mx = -1;
int last = -1;
for(int i=remain-1; i>=0; i--){
if(mx<dp[i]){
mx = dp[i];
last = i;
}
}
cout<<"Case "<<kase++<<": "<<mx+1<<" "<<last+678<<endl;
}
return 0;
}
矩阵的链乘（区间dp）
将问题转化为n-1矩阵的相乘
时间复杂度是(O(n^3))
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
int a[maxn];
int dp[maxn][maxn];
int n;
struct Matrix{
int x, y;
}node[maxn];
int main(){
ios::sync_with_stdio(false);
while(cin>>n){
for(int i=1; i<=n; i++) cin>>a[i];
node[1].x=a[1] ,node[1].y=a[2];
for(int i=2; i<=n-1; i++){
node[i].x=a[i], node[i].y=a[i+1];
}
cls(dp, 0x3f);
for(int i=1; i<=n-2; i++){
dp[i][i+1] = node[i].x*node[i].y*node[i+1].y;
}
for(int i=1; i<=n-1; i++) dp[i][i] = 0;
for(int l=3; l<=n-1; l++){
for(int i=1; i<=n-l+1; i++){
int j=i+l-1;
for(int k=i; k<=j; k++){
//cout<<i<<" "<<k<<" "<<j<<endl;
if(dp[i][k]!=inf&&dp[k+1][j]!=inf)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+node[i].x*node[k].y*node[j].y);
}
}
}
//cout<<dp[1][4]<<endl;
cout<<dp[1][n-1]<<endl;
}
return 0;
}
uva 1626 括号完整匹配(区间dp)
这道题的输入正的是蜜汁奇怪， 括号还可以是空串，输入间还要有空行。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
int dp[maxn][maxn];
char s[105];
bool match(char x, char y){
if(x == '(' && y == ')') return true;
if(x == '[' && y == ']') return true;
return false;
}
void print(int l, int r){
if(l>r) return;
if(l == r){
if(s[l]=='('||s[r] == ')') cout<<"()";
else cout<<"[]";
return ;
}
int ans = dp[l][r];
if(match(s[l], s[r])&&ans == dp[l+1][r-1]){
cout<<s[l]; print(l+1, r-1); cout<<s[r];
return ;
}
else{
for(int i=l; i<r; i++){
if(ans ==dp[l][i]+dp[i+1][r]){
print(l, i), print(i+1, r);
break;
}
}
return ;
}
}
int main(){
ios::sync_with_stdio(false);
int _;
scanf("%d", &_);
getchar();
while(_--){
int idx = 0;
gets(s);
while(s[idx] =getchar()){
if(s[idx] == '
') break;
idx++;
}
s[idx] = ' ';
//cout<<s<<'
';
int len = strlen(s);
//cls(dp, 0x3f);
for(int i=0; i<len; i++) {
dp[i][i] = 1;
dp[i+1][i] = 0;
}
for(int i=len-2; i>=0; i--){
for(int j=i+1; j<len; j++){
dp[i][j] = len;
if(match(s[i], s[j])) dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
for(int k=i; k<j; k++){
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
}
}
}
//cout<<dp[0][len-1]<<endl;
print(0, len-1);
cout<<endl;
if(_) cout<<endl;
}
return 0;
}
一个任意的多边形(不一定是凸)剖分的三角形最大面积最小
一个判断是否是凸的+区间dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
struct Node{
int x, y;
}node[maxn];
int n;
double dp[maxn][maxn];
double area(Node a, Node b, Node c){
return 1.0*abs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2.0;
}
bool is_convex(int x, int y, int z){
double S = area(node[z], node[x], node[y]);
for(int i=1; i<=n; i++){
if(i == x || i == y || i == z) continue;
double s = area(node[i], node[x], node[y])+area(node[i], node[x], node[z])+area(node[i], node[z], node[y]);
//点在内部，肯定非凸
if(fabs(s-S)<1e-4) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n;
for(int i=1; i<=n; i++) cin>>node[i].x>>node[i].y;
for(int l=3; l<=n; l++){
for(int i=1; i<=n-l+1; i++){
int j = i+l-1;
if(j>n) continue;
dp[i][j] = 1000000000.0;
for(int k=i+1; k<j; k++){
if(!is_convex(i, k, j)) continue;
//cout<<area(node[i], node[k], node[j])<<endl;
dp[i][j] = min(dp[i][j], max(max(dp[i][k], dp[k][j]), area(node[i], node[k], node[j])));
}
}
}
//cout<<dp[1][n]<<endl;
cout<<fixed<<setprecision(1);
cout<<dp[1][n]<<endl;
}
return 0;
}
uva1025 A spy in the metro
一个人要在T秒的在n站见一个人，使得他在__中途等待的时间最短__, 而不是花费的总时间。
因为终点确定了，所以要倒着dp,不然开始的状态太多了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int n, t;
bool has_train[55][205][2];
int dp[55][205];
int a[maxn];
int main(){
ios::sync_with_stdio(false);
int kase = 1;
while(cin>>n&&n){
cin>>t;
for(int i=1; i<=n-1; i++) cin>>a[i];
cls(has_train, 0);
int m1;
cin>>m1;
for(int i=1; i<=m1; i++){
int temp;
cin>>temp;
has_train[1][temp][0] = true;
int tot = temp;
for(int j=1; j<n; j++){
tot += a[j];
has_train[j+1][tot][0] = true;
}
}
cin>>m1;
for(int i=1; i<=m1; i++){
int temp;
cin>>temp;
has_train[n][temp][1] = true;
int tot = temp;
for(int j=n-1; j>=1; j--){
tot += a[j];
has_train[j][tot][1] = true;
}
}
cls(dp, 0x3f);
//for(int i=0; i<=t-1; i++) dp[n][i] = inf;
dp[n][t] = 0;
for(int i=t-1; i>=0; i--){
for(int j=1; j<=n; j++){
dp[j][i] = dp[j][i+1]+1;
if(j<n&&has_train[j][i][0]&&i+a[j]<=t){
dp[j][i] = min(dp[j][i], dp[j+1][i+a[j]]);
}
if(j>1&&has_train[j][i][1]&&i+a[j-1]<=t){
dp[j][i] = min(dp[j][i], dp[j-1][i+a[j-1]]);
}
}
}
if(dp[1][0]<inf)
cout<<"Case Number "<<kase++<<": "<<dp[1][0]<<"
";
else cout<<"Case Number "<<kase++<<": impossible
";
}
return 0;
}
/*
3
3
1 2
1 0
1 0
*/
uva 437 巴比伦
每个方块的个数没有限制，将状态进行了相应的映射，使得状态量变小。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int block[35][3];
int dp[35][35];
int n;
void get(int* v1, int x, int y){
int idx=0;
bool has = false;
for(int i=0; i<3; i++){
if(i == y) continue;
else v1[idx++] = block[x][i];
}
}
int dfs(int u, int v){
int& ans = dp[u][v];
//cout<<u<<" "<<v<<endl;
if(ans>0) return ans;
int v1[2], v2[2];
get(v1, u, v);
for(int i=1; i<=n; i++){
for(int j=0; j<3; j++){
get(v2, i, j);
//cout<<v1[0]<<" "<<v1[1]<<endl;
//cout<<v2[0]<<" "<<v2[1]<<endl;
if(v2[0]<v1[0]&&v2[1]<v1[1]){
ans = max(ans, dfs(i, j));
}
}
}
ans+=block[u][v];
return ans;
}
int main(){
ios::sync_with_stdio(false);
int kase = 1;
while(cin>>n&&n){
for(int i=1; i<=n; i++){
for(int j=0; j<3; j++) cin>>block[i][j];
sort(block[i], block[i]+3);
}
int ans = 0;
cls(dp, 0);
for(int i=1; i<=n; i++){
for(int j=0; j<3; j++){
ans = max(ans, dfs(i, j));
}
}
cout<<"Case "<<kase++<<": maximum height = "<<ans<<endl;
}
return 0;
}
最小汉哈顿距离
又是一个倒着更新的例子。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
double dp[maxn][maxn];
double dist[maxn][maxn];
int x[maxn], y[maxn];
int n;
int main(){
ios::sync_with_stdio(false);
while(cin>>n){
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++) {
dist[i][j] = sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
}
}
for(int i=n-1; i>=2; i--){
//规定i>j;
for(int j=i-1; j>=1; j--){
if(i == n-1) dp[i][j] = dist[n-1][n]+dist[j][n];
else dp[i][j] = min(dp[i+1][j]+dist[i][i+1], dp[i+1][i]+dist[j][i+1]);
}
}
cout<<fixed<<setprecision(2);
cout<<dp[2][1]+dist[1][2]<<endl;
}
return 0;
}
切割木棒
切割n次，每一次的花费是该木棒的长度
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 50+10;
int dp[maxn][maxn];
int l;
int n;
int a[maxn];
int dfs(int i, int j){
if(i>=j-1) return 0;
int &ans = dp[i][j];
if(ans>0) return ans;
ans = inf;
for(int k=i+1; k<j; k++){
ans = min(ans, dfs(i, k)+dfs(k, j));
}
ans += (a[j]-a[i]);
return ans;
}
int main(){
ios::sync_with_stdio(false);
while(cin>>l&&l){
cin>>n;
cls(dp, 0);
for(int i=1; i<=n; i++) cin>>a[i];
a[0] = 0, a[n+1] = l;
cout<<"The minimum cutting is "<<dfs(0, n+1)<<".
";
}
return 0;
}
树形dp
uva 12186 工人的请愿书
直属的下属在超过T%的人数之后，就会向直属上司进行报告。每一个人最少有(son[u]*T-1)/100+1;
一种向上取整的方法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int n, t;
vector<int> son[maxn];
vector<int> val[maxn];
int dp[maxn];
int dfs(int u){
if(son[u].empty()) return 1;
int &ans = dp[u];
for(int i=0; i<son[u].size(); i++){
int v = son[u][i];
val[u].push_back(dfs(v));
}
//一种算下线的方法。
int mi = (son[u].size()*t-1)/100+1;
sort(val[u].begin(), val[u].end());
for(int i=0; i<mi; i++) ans += val[u][i];
return ans;
}
int main(){
ios::sync_with_stdio(false);
while(cin>>n>>t&&n+t){
for(int i=0; i<=n; i++) son[i].clear(), val[i].clear();
for(int i=0; i<=n; i++) dp[i] = 0;
for(int i=1; i<=n; i++){
int temp;
cin>>temp;
son[temp].push_back(i);
}
cout<<dfs(0)<<endl;
}
return 0;
}
老师教书(状压dp)
ans>=0是已经被访问过的条件
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 1e9;
const int maxn = 120+10;
int c[maxn];
int s, m, n;
int dp[maxn][1<<8][1<<8];
int jiao[maxn];
int dfs(int u, int s0, int s1, int s2){
if(u == n+m+1) return s2==(1<<s)-1?0:inf;
int &ans = dp[u][s1][s2];
//ans>=不是>
if(ans>=0) return ans;
ans = inf;
if(u>m) ans = min(ans, dfs(u+1, s0, s1, s2));
//m0表示即将0->1人教的课。
int m0 = (jiao[u]&s0), m1 = (jiao[u]&s1);
//|是一种教课程的运算, ^是一种减课程的运算
s0 = (s0^m0), s1 = (s1^m1)|(m0), s2 = (s2|m1);
ans = min(ans, dfs(u+1, s0, s1, s2)+c[u]);
return ans;
}
int main(){
string line;
int x;
bool flag = false;
while(getline(cin, line)){
stringstream ss(line);
ss >> s >> m >> n;
if(s == 0) break;
for(int i = 1; i <= m+n; i++) {
getline(cin, line);
stringstream ss(line);
ss >> c[i];
jiao[i] = 0;
while(ss >> x) jiao[i] |= (1<<(x-1));
}
//memset(dp, -1, sizeof(dp));
cls(dp, -1);
cout << dfs(1, (1<<s)-1, 0, 0) << "
";
}
return 0;
}
uva 1252 (状压dp)
最多11个特征，n个物品，问最多问多少次能一定确定一个物品。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 128+5;;
const int maxm = 11;
int d[1<<maxm][1<<maxm];
string feature[maxn];
bool vis[1<<maxm][1<<maxm];
int m, n;
int cnt[1<<maxm][1<<maxm];
int dp(int s, int a){
if(cnt[s][a]<=1) return 0;
if(cnt[s][a] == 2) return 1;
int &ans = d[s][a];
if(vis[s][a]) return ans;
vis[s][a] = true;
ans = inf;
for(int i=0; i<m; i++){
if(!(s&(1<<i))){
int s1 = s^(1<<i), a1 = a^(1<<i);
//增加一个i特征的询问
d[s][a] = min(d[s][a], (max(dp(s1, a1), dp(s1, a))+1));
}
}
return ans;
}
void init(){
for(int s=0; s<(1<<m); s++){
for(int a=s; a; a=(a-1)&s){
cnt[s][a] = 0;
}
cnt[s][0] = 0;
}
for(int i=0; i<n; i++){
int tot = 0;
for(int j=0; j<m; j++){
if(feature[i][j] == '1'){
tot += (1<<j);
}
}
for(int s=0; s<(1<<m); s++){
cnt[s][s&tot]++;
}
}
}
int main(){
ios::sync_with_stdio(false);
int kase = 1;
while(cin>>m>>n&&n+m){
for(int i=0; i<n; i++) cin>>feature[i];
init();
cls(vis, 0);
cout<<dp(0, 0)<<"
";
kase++;
}
return 0;
}
LCS 转化为LIS
两个序列中，每一个序列里面的数字都只出现了一次，因此可以来转化
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 250*250+10;
int a[maxn], b[maxn];
int c[maxn];
int n, p, q;
map<int, int> mp;
int g[maxn];
int d[maxn];
int main(){
ios::sync_with_stdio(false);
int kase = 1;
int _;
cin>>_;
while(_--){
cin>>n>>p>>q;
mp.clear();
for(int i=1; i<=p+1; i++) cin>>a[i], mp[a[i]] = i;
for(int i=1; i<=q+1; i++) cin>>b[i];
int idx = 1;
for(int i=1; i<=q+1; i++) if(mp[b[i]])c[idx++] = mp[b[i]];
// for(int i=1; i<=q; i++) cout<<b[i]<<" ";
// cout<<endl;
int ans = 0;
cls(g, 0x3f);
for(int i=1; i<idx; i++){
int k=lower_bound(g+1, g+idx, c[i])-g;
d[i] = k;
g[k] = c[i];
ans = max(ans, d[i]);
}
cout<<"Case "<<kase++<<": "<<ans<<endl;
}
return 0;
}
/*
1
10 7 8
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
*/
约瑟夫环
[f[i] = (f[i-1]+k)\%i
]
由于是从m号开始的，(f[n] = (m-k+1+f[n])\%n), 最后判断f[n]<=0是否成立，否则+n.
初始化(f[1] = 0)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
int d[maxn];
int n, k, m;
int main(){
ios::sync_with_stdio(false);
while(cin>>n>>k>>m&&n+k+m){
d[1] = 0;
for(int i=2; i<=n; i++){
d[i] = (d[i-1]+k)%i;
}
d[n] = (m-k+1+d[n])%n;
if(d[n]<=0) d[n]+=n;
cout<<d[n]<<endl;
}
return 0;
}
博弈+dp
(dp[i][j]表示(i, j)区间先手的取的最大值)
时间复杂度是(O(n^2))
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 200+10;
int a[maxn];
int dp[maxn][maxn];
int z[maxn][maxn], y[maxn][maxn];
int n;
int pre[maxn];
int main(){
ios::sync_with_stdio(false);
while(cin>>n&&n){
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dp[i][j] = -inf;
for(int i=1; i<=n; i++){
cin>>a[i];
pre[i] = pre[i-1]+a[i];
}
for(int i=1; i<=n; i++) dp[i][i] = z[i][i] = y[i][i] = a[i];
for(int l=1; l<=n; l++){
for(int i=1; i<=n-l; i++){
int j=i+l;
int mi = 0;
mi = min(mi, y[i][j-1]);
mi = min(mi, z[i+1][j]);
dp[i][j] = max(dp[i][j], pre[j]-pre[i-1]-mi);
y[i][j] = min(y[i][j-1], dp[i][j]);
z[i][j] = min(z[i+1][j], dp[i][j]);
}
}
cout<<2*dp[1][n]-pre[n]<<endl;
}
return 0;
}
停掉最多的服务(状压dp)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 17;
int cover[1<<maxn];
int d[1<<maxn];
int graph[maxn];
int n;
int main(){
ios::sync_with_stdio(false);
int kase = 1;
while(cin>>n&&n){
int m;
cls(graph, 0);
cls(cover, 0);
for(int i=0; i<n; i++){
cin>>m;
int v;
graph[i] = (1<<i);
for(int j=0; j<m; j++) {
cin>>v;
graph[i] |= (1<<v);
}
}
for(int s=1; s<(1<<n); s++){
for(int i=0; i<n; i++){
if(s&(1<<i)){
cover[s] |= graph[i];
}
}
}
cls(d, 0);
d[0] = 0;
for(int s=1; s<(1<<n); s++){
for(int s0=s; s0; s0=(s0-1)&s){
if(cover[s0] == (1<<n)-1){
//s0已经可以停掉一个服务了，剩下接着找。
d[s] = max(d[s^s0]+1, d[s]);
}
}
}
cout<<"Case "<<kase++<<": "<<d[(1<<n)-1]<<endl;
}
return 0;
}
森林的最小点覆盖+最多的一条边被两点覆盖
树形dp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
const int M = 2000;
vector<int> G[maxn];
int n, m;
bool vis[maxn][2];
int d[maxn][2];
int dp(int u, int state, int p){
if(vis[u][state]) return d[u][state];
vis[u][state] = true;
int &ans = d[u][state];
//点亮该灯
ans=M;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(p!=v){
ans += dp(v, 1, u);
}
}
if(state == 0&&p>=0) ans++;
//不点该灯
if(p<0||state == 1){
int ans1=0;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(p!=v){
ans1 += dp(v, 0, u);
}
}
if(p>=0) ans1++;
ans = min(ans, ans1);
}
//若父亲没点，这条边仅一次被点亮
return ans;
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n>>m;
int u, v;
for(int i=0; i<n; i++) G[i].clear(), d[i][0] = d[i][1] = 0, vis[i][0] = vis[i][1] = false;
for(int i=1;i<=m; i++){
cin>>u>>v;
G[u].push_back(v), G[v].push_back(u);
}
int ans = 0;
for(int i=0; i<n; i++){
if(!vis[i][0]){
ans += dp(i, 0, -1);
}
}
cout<<ans/2000<<" "<<m-(ans%2000)<<" "<<ans%2000<<endl;
}
return 0;
}
带有滑动窗口的线性dp
按序取垃圾，使得最后的经过的距离最短。
注意条件：垃圾重量是单调增的，所以可以使用滑动窗口。
uva的PE居然显示的是WA。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int C;
struct Node{
int x, y, weight;
}node[maxn];
int pre_dist[maxn];
int pre_weight[maxn];
int pre[maxn];
int n;
int d[maxn];
int q[maxn];
int get(int j){
return d[j]+abs(node[j+1].x)+abs(node[j+1].y)-pre[j+1];
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>C;
cin>>n;
int x, y, w;
pre[0] = 0;
pre_weight[0] = pre_dist[0] = 0;
for(int i=1; i<=n; i++){
cin>>x>>y>>w;
node[i] = Node{x, y, w};
pre_weight[i] = pre_weight[i-1]+w;
pre[i] = pre[i-1]+abs(x-node[i-1].x)+abs(y-node[i-1].y);
}
int l, r;
l=r=1;
q[l] = 0;
cls(d, 0x3f);
d[0] = 0;
for(int i=1; i<=n; i++){
while(l<=r&&pre_weight[i]-pre_weight[q[l]]>C)l++;
d[i] = min(d[i], get(q[l]));
d[i] += (pre[i]+abs(node[i].x)+abs(node[i].y));
//cout<<i<<" "<<d[i]<<endl;
while(l<=r&&get(q[r])>=get(i))r--;
q[++r] = i;
}
cout<<d[n]<<endl;
if(_>0) cout<<endl;
}
return 0;
}
内否切割成目标的矩形块(状压dp)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 15;
int n, x, y;
int a[maxn];
int d[1<<maxn][105];
bool vis[1<<maxn][105];
int s[1<<maxn];
int cou(int x){
return x==0?0:cou(x/2)+(x&1);
}
int dp(int S, int x){
if(vis[S][x]) return d[S][x];
vis[S][x] = true;
int &ans = d[S][x];
if(cou(S) == 1) return ans = 1;
int y = s[S]/x;
for(int s1=(S-1)&S; s1; s1=(s1-1)&S){
int s2 = S-s1;
//沿y切
if(s[s1]%x == 0&&dp(s1, min(x, s[s1]/x))&&dp(s2, min(x, s[s2]/x))) return ans=1;
if(s[s1]%y == 0&&dp(s1, min(y, s[s1]/y))&&dp(s2, min(y, s[s2]/y))) return ans=1;
}
return ans=0;
}
int main(){
ios::sync_with_stdio(false);
int kase = 1;
while(cin>>n){
if(!n) break;
cls(vis, 0);
cin>>x>>y;
for(int i=0; i<n; i++) cin>>a[i];
cls(s, 0);
for(int i=0; i<(1<<n); i++){
for(int j=0; j<n; j++) if(i&(1<<j)) s[i] += a[j];
}
int ans = 0;
//cout<<s[(1<<n)-1]<<endl;
if(s[(1<<n)-1]!=x*y||s[(1<<n)-1]%x) ans = 0;
else ans = dp((1<<n)-1, min(x, y));
if(ans){
cout<<"Case "<<kase++<<": Yes"<<endl;
}
else{
cout<<"Case "<<kase++<<": No"<<endl;
}
}
return 0;
}
分割团队(正负背包)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
bool vis[maxn];
int G[maxn][maxn];
int color[maxn];
vector<int> team[maxn][2];
int no;
int d[maxn][maxn<<1];
int diff[maxn];
int n;
bool dfs(int x, int col){
color[x] = col;
//cout<<x<<" "<<col<<endl;
team[no][col-1].push_back(x);
for(int i=1; i<=n; i++){
if(i == x) continue;
if(!(G[i][x]&&G[x][i])){
if(color[i] == col) return false;
if(!color[i]&&!dfs(i, 3-col)) return false;
}
}
return true;
}
bool build(){
cls(color, 0);
no = 0;
for(int i=1; i<=n; i++){
if(!color[i]){
team[no][0].clear(), team[no][1].clear();
if(!dfs(i, 1)) return false;
diff[no] = team[no][0].size()-team[no][1].size();
no++;
}
}
return true;
}
void prin(int ans){
vector<int> team1, team2;
for(int i=no-1; i>=0; i--){
int t;
//cout<<i<<" "<<ans<<endl;
if(d[i][ans+n-diff[i]]){
t=0;
ans -= diff[i];
}
else{
t =1;
ans += diff[i];
}
//cout<<ans<<endl;
for(int j=0; j<team[i][t].size(); j++){
team1.push_back(team[i][t][j]);
}
for(int j=0; j<team[i][t^1].size(); j++){
team2.push_back(team[i][t^1][j]);
}
}
cout<<team1.size();
for(int i=0; i<team1.size(); i++) cout<<" "<<team1[i];
cout<<endl;
cout<<team2.size();
for(int i=0; i<team2.size(); i++) cout<<" "<<team2[i];
cout<<endl;
}
void dp(){
cls(d, 0);
d[0][0+n] = 1;
for(int i=0; i<no; i++){
for(int j=-n; j<=n; j++) if(d[i][j+n]){
d[i+1][j+n+diff[i]] = 1;
d[i+1][j+n-diff[i]] = 1;
}
}
for(int ans = 0; ans<=n; ans++){
if(d[no][ans+n]) {prin(ans); return;}
if(d[no][-ans+n]) {prin(-ans); return;}
}
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n;
cls(G, 0);
for(int i=1; i<=n; i++){
int id;
while(cin>>id&&id){
G[i][id] = 1;
}
}
if(n==1||!build()) cout<<"No solution
";
else{
dp();
}
if(_) cout<<"
";
}
return 0;
}
/*
2
5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
*/
兑换货币(正负背包)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int num[10];
int dp[maxn];
int main(){
ios::sync_with_stdio(false);
int _;
scanf("%d", &_);
while(_--){
for(int i=1; i<=6; i++) scanf("%d", &num[i]);
for(int i=1; i<=2000; i++) dp[i] = inf;
dp[0] = 0;
for(int i=1; i<=6; i++){
for(int j=num[i]; j<=2000; j++){
dp[j] = min(dp[j], dp[j-num[i]]+1);
}
}
for(int i=1; i<=6; i++){
for(int j=2000-num[i]; j>=0; j--){
dp[j] = min(dp[j], dp[j+num[i]]+1);
}
}
int ans = 0;
int mx = -1;
for(int i=1;i<=100; i++){
mx = max(mx, dp[i]);
ans += dp[i];
}
printf("%.2lf %d
", double(ans)/100.0, mx);
}
return 0;
}