Description 给出 N 个点M 条边的无向图，定向得到有向无环图，使得最长路最短。
N ≤ 15, M ≤ 100
Solution 【DP|[BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理】大家都知道Dilworth定理的其中一个内容：最小路径覆盖=最长反链。
实际上与之相似的是：最长路=最小反链划分数。
这个东西虽然比较显然，但是之前没有接触过的话可能还是比较难想到。
有了这个，直接状压DP就行了。
Code
#include
using namespace std;
#define LL long long
#define pa pair
const int inf=2147483647;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n=0,m,to[16],v[16];
bool ok[1<<15];
int f[1<<15];
char s1[3],s2[3];
struct Edge{int x,y;
}e[110];
int main()
{
m=read();
for(int i=1;
i<=m;
i++)
{
scanf("%s%s",s1,s2);
int x=s1[0]-'L'+1,y=s2[0]-'L'+1;
if(!v[x])v[x]=++n;
if(!v[y])v[y]=++n;
e[i].x=v[x],e[i].y=v[y];
}
for(int S=1;
S<(1< 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）