1.约瑟夫问题的变形(LA 3882)
题意：
\(n\)个数排成一个圈。第一次删除\(m\)，以后每数\(k\)个数删除一次，求最后一个被删除的数。
f[1]=0;//最后剩下的人为0
//然后一步一步回到它一开始的编号
for(int i=2;i<=n;++i)
{
f[i]=(f[i-1]+k)%i;//每一轮都会重新编号
}
int ans=(m-k+1+f[n])%n;//beginpos+k=m-> beginpos=m-k,又要把f[n]的编号加上一
if(ans<=0) ans+=n;
printf("%d\n",ans);2.王子和公主\((UVa10635)\)
题意：
一个王子和公主在\(n*n\)的格子中行走，这些格子是有\(1....n^2\)的编号的。现在给定\(p+1\)个数，再给定\(q+1\)个数，公主和王子可以选择其中某些格子行走，求他们最多能走几个相同的格子。
分析：
思路很巧妙，表面看本题是一个\(LCS\)问题
注意到序列中的数均不相同，因此可以把A中的数重新编号为\(1\)~\(p+1\)
例如：\(A={1,7,5,4,8,3,9},B={1,4,3,5,6,2,8,9}\),因此可以把\(A\)重新编号为\({1,2,3,4,5,6,7}\)，而\(B\)就应为\({1,4,6,3,0,0,5,7}\)，其中\(0\)表示元素没有在\(A\)中出现过（事实上，可以直接删除这样一些元素），这时，\(A\)与\(B\)的\(LCS\)就为新的\(B\)的\(LIS\)
，于是我们就将一个\(LCS\)问题转化为了\(LIS\)（这一定是在\(A\)中的元素各不相同的前提下进行的）
\(Code:\)
scanf("%d%d%d",&N,&p,&q);
memset(num,0,sizeof(num));
for(int i=1;i<=p+1;++i)
{
int x;
scanf("%d",&x);
num[x]=i;
}
int n=0;
for(int i=1;i<=q+1;++i)
{
int x;
scanf("%d",&x);
s[++n]=num[x];
}
for(int i=1;i<=n;++i) g[i]=inf;
int ans=0;
for(int i=1;i<=n;++i)
{
int k=lower_bound(g+1,g+n+1,num[i])-g;
g[k]=num[i];
d[i]=k;
ans=max(ans,k);
}3.黑客的攻击状压
题意：
假如你是一个黑客，侵入了一个有着n台计算机（编号为1.2.3....n）的网络。一共有n种服务，每台计算机都运行着所有服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务（如果其中一些服务已经停止，那他们继续保持停止状态）。你的目标是让尽量多的服务完全瘫痪(即：没有任何计算机运行着该服务)
个人认为，状态压缩类型的题一般编号都从0开始写起比较保险。
抽象：
本题的数学模型为：把n个集合P1,P2,...,Pn分成尽量多组，使得每组中所有集合的并集等于全集。
\(Code:\)
for(int i=0;i<n;++i)
{
p[i]=(1<<i);
int m;
scanf("%d",&m);
while(m--)
{
int member;
scanf("%d",&member);
p[i]|=(1<<member);
}
}
for(int i=0;i<(1<<n);++i)//子集的集合i
{
for(int j=0;j<n;++j)
{
if(i&(1<<j))
{
cover[i]|=p[j];
}
}
}
for(int i=0;i<(1<<n);++i)
{
for(int s=i;s;s=(s-1)&s)//枚举子集
{
if(cover[s]==(1<<n)-1)
{
ans[i]=max(ans[i],ans[i^s]+1);
}
}
}4.放置街灯(UVa10859)
题意：
给定一个\(n\times n\)个点\(m\times m\)条边的无向无环图，在尽量少的节点上放灯，使得所有边都与灯相邻（被灯照亮）。
在灯的总数最小的前提下，被两盏灯同时照亮的边数应该尽可能大。
分析：
在不考虑边数尽量大这一条件时，就是一个简单的树形\(dp\)（虽然我在昨天晚上也就是刚写了一句话的时候并不这么觉得）
一个超级厉害（反正我正常来讲现在都想不出来）的一个优化：首先本题的优化目标有两个：放置的灯数\(a\)尽量少，被两盏灯同时照亮的边数\(b\)尽量大
为了统一起见，我们把第二个条件改为：恰好被一盏灯照亮的边数c尽量小（因为要求所有边都要被照亮）。然后改用\(x=Ma+c\)作为最小化的目标，其中\(M\)为一个很大的正整数。当\(x\)取到最小值时，\(x/M\)的整数部分就是\(a\),\(x\%M\)就是\(c\)。
一般来说：如果有两个需要优化的量\(v1\)和\(v2\)，要求首先满足\(v1\)最小，在\(v1\)相同的情况下\(v2\)最小，则可以把二者组合成一个量\(Mv1+v2\)，其中\(M\)是一个比“\(v2\)的最大理论值和\(v2\)的最小理论值之差”还要大的数。这样，只有两个解的\(v1\)不同，则不管\(v2\)相差多少，都是\(v1\)起到决定性作用；只有当\(v1\)相同时，才取决于\(v2\)。在本题中，可以取\(M=2000\)。
\(Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int M=2000;
const int maxn=1010;
int d[maxn][2];
vector<int> g[maxn];
int T,n,m;
int vis[maxn];
void dfs(int u)
{
vis[u]=1;
d[u][0]=0;
d[u][1]=M;
for(int i=0;i<g[u].size();++i)
{
if(vis[g[u][i]]) continue;
dfs(g[u][i]);
d[u][0]+=d[g[u][i]][1]+1;
d[u][1]+=min(d[g[u][i]][0]+1,d[g[u][i]][1]);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
g[i].clear();
}
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d%d",&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])
{
dfs(i);
ans+=min(d[i][0],d[i][1]);
}
}
printf("%d %d %d\n",ans/M,m-ans%M,ans%M);
}
return 0;
}\(5.\)捡垃圾的机器人\((UVa1169)\)
题意：
有\(n\)个垃圾，第\(i\)个垃圾的坐标为\((x_i,y_i)\)，重量为\(w_i\)。有一个机器人，要按照编号从小到大的顺序捡起所有垃圾并扔进垃圾桶（垃圾桶在原点\((0,0)\)）。机器人可以捡起几个垃圾以后一起扔掉，但任何时候其手中的垃圾总重量不能超过最大载重\(C\)。两点间的行走距离为曼哈顿距离（即横坐标之差的绝对值加上纵坐标之差的绝对值）。求出机器人行走的最短总路程（一开始，机器人在\((0,0)\)处）。
输入格式：
输入的第一行为数据组数。每组数据的第一行为最大承重\(C(1<=C<=100)\)；第二行为正整数\(n(1<=n<=100000)\)，即垃圾的数量；以下\(n\)行每行为两个非负整数\(x,y\)和一个正整数\(w\)，即坐标和重量（重量保证不超过\(C\)）。
分析：
如果把当前的“垃圾序号”以及“当前载重量”作为状态，则状态个数就已经高达\(O(NC)\)，不管怎么优化转移，时间也无法承受。所以我们只能够设一维的转移方程，设\(d(i)\)表示将前\(i\)个垃圾处理完（即已经放到了垃圾桶里）所需要的最短距离，则
\(d(i)=min(d[i],d[j]+enter_0(j+1)+dis(j+1,i)+enter_0(i))\)//\(enter_0(i)\)是指\(0\)到\(i\)的距离
解释一下，就是：处理完前i个的最短距离，等于处理完前j个的最短距离+从原点返回到第\(j+1\)个点，再从第\(j+1\)个点一直走到第\(i\)个点（他们中间的这些点也要走），再从第i个点到0点。
要满足的条件就是\(w(j+1,i)<=C\)。
我们首先采用前缀和进行优化，则\(dist(j+1,i)=sumdis[i]-sumdis[j+1]\)
原式可优化为\(d(i)=min(d[j]+enter_0(j+1)-sumdis[j+1])+enter_0(i)+sumdis[i]\);
我们将取\(min\)的这一部分再进行优化，将它定义为一个函数\(func(j)\)，则显然可以使用双端队列（或者单调队列）来进行优化。
因为对于一个新的元素，如果在队尾的元素的\(func\)比它大，又因为它在之前就已经进入了队列，所以寿命肯定会比这个新的元素短，故我们将这种已经没有价值的元素弹出队列。
以双端队列为例：队头存的是最优的元素，每次先弹出\(w\)已经不满足的队头元素，再用队头的元素来更新当前元素，然后插入这个元素，就用上一段的方法。
\(Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=100010;
template<class T>void read(T &x)
{
bool f=0;char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
if(f) x=-x;
}
struct Node
{
int x,y,w;
}a[maxn];
int dist(int i,int j)
{
return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
}
int sumw[maxn];
int sumdis[maxn];
int d[maxn];
int func(int i)
{
return d[i-1]+dist(0,i)-sumdis[i];
}
int main()
{
int T;
read(T);
while(T--)
{
int n,C;
read(C);read(n);
deque<int> dq;
memset(sumw,0,sizeof(sumw));
memset(sumdis,0,sizeof(sumdis));
memset(d,0,sizeof(d));
a[0].x=a[0].y=0;
for(int i=1;i<=n;++i)
{
read(a[i].x);read(a[i].y);read(a[i].w);
sumw[i]=sumw[i-1]+a[i].w;
sumdis[i]=sumdis[i-1]+dist(i-1,i);
}
for(int i=1;i<=n;++i)
{
while(!dq.empty()&&func(i)<=func(dq.back())) dq.pop_back();
dq.push_back(i);//可以自己更新自己
while(!dq.empty()&&sumw[i]-sumw[dq.front()-1]>C) dq.pop_front();
d[i]=func(dq.front())+sumdis[i]+dist(0,i);
}
printf("%d\n",d[n]);
if(T)
{
printf("\n");
}
}
return 0;
}\(6\).分享巧克力
看到这道题的第一眼：不会是状压吧
看到题解：还真是状压
后来想想我怎么会这么聪明呢
原来我看的就是题解
我们设状态转移方程为f(r,c,S)表示的是r*c的蛋糕是否可以切割成面积集合为S的蛋糕。
但实际上我们只需要二维的状态转移方程，因为我们可以通过S和r来算出c\(或者无解\)
原文：https://www.cnblogs.com/iwillenter-top1/p/11768436.html