【TJOI2015】组合数学

Source

TJOI2015
bzoj5481

Hint

请先思考后再展开

转dag,求最小链覆盖

Solution

请先思考后再展开

根据Dilworth定理,最小链覆盖=最小反链
然后每个点按权值拆开来,他们一定在同一条反链上
然后他一定是形如一个递增序列的
那么dp(i,j)表示结尾在(i,j)右上角的最长反链
然后就可以直接dp了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[MAX_N][MAX_N];
ll f[MAX_N][MAX_N];
void main()
{
int T=qread();
while(T--)
{
int n=qread(),m=qread();memset(f,0,sizeof f);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=qread();
for(int i=1;i<=n;i++) for(int j=m;j>=1;j--)
f[i][j]=max( max(f[i-1][j],f[i][j+1]),f[i-1][j+1]+a[i][j] );
write2(f[n][1]);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ad32.html
转载请注明出处,谢谢!