相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3997
神犇题解：http://blog.csdn.net/popoqqq/article/details/45171469
解题报告
这题又™是结论题
需要用到的结论：
Dilworth定理：DAG的最小链覆盖=最大点独立集
类似的结论还有：
最大团=补图上的最小点覆盖的补集
最大反链的大小=最小链划分
最大链的大小=最小反链划分
知道结论之后，实际上就是让你求一些点，相互不能到达，且点权和最大
这样的话，从左下到右上搞一个DP就可以了！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1000+9;
int n,m,val[N][N],f[N][N],g[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int main() {
for (int T=read();T;T--) {
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
m = read(); n = read();
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
val[i][j] = read();
}
}
for (int i=1;i<=n;i++) {
for (int j=m,cur=0;j;j--) {
f[i][j] = cur + val[i][j];
cur = max(cur, g[j]);
g[j] = max(g[j], f[i][j]);
}
}
int vout = 0;
for (int i=1;i<=m;i++)
vout = max(vout, g[i]);
printf("%d\n",vout);
}
return 0;
}
Thank you for another informative website. Where else could I get that kind of info written in such a perfect way? I have a project that I am just now working on, and I have been on the look out for such info.
854621 335420I view something genuinely particular in this site . 205068
135208 620882I dont agree with this particular post. However, I did researched in Google and Ive discovered out that you are correct and I had been thinking within the incorrect way. Continue producing quality material comparable to this. 45756
942148 869262This post contains excellent original thinking. The informational content material here proves that things arent so black and white. I feel smarter from just reading this. 598839
438074 129075Directories such given that the Yellow Websites need not list them, so unlisted numbers strength sometimes be alive a lot more harm than financial assistance. 561636
351766 207059Nice article. It does shed some light on the issue. By the for those interested in binary options can get an exclusive binary options bonus. 92037
343580 510280We stumbled over here coming from a different internet page and thought I may possibly check issues out. I like what I see so now im following you. Appear forward to exploring your internet page however again. 197358
574960 39664I believe this internet site has some rattling fantastic information for everybody : D. 600996
181288 573483Greatest fighter toasts ought to entertain and supply prize on your couples. Initially audio system next to obnoxious crowd would be wise to understand 1 certain gold colored strategy as to public speaking, which is individual interests self. very best man jokes 641506
79744 49333Woh I like your content , saved to bookmarks ! . 111519
103444 592642Woh I like your content material , saved to favorites ! . 559122
881342 310817Quite fascinating info!Perfect just what I was looking for! 33702
867674 387686Hi there, just became aware of your blog by way of Google, and found that its genuinely informative. Im gonna watch out for brussels. Ill be grateful should you continue this in future. Numerous men and women is going to be benefited from your writing. Cheers! 401771
After all, what a great site and informative posts, I will upload inbound link – bookmark this web site? Regards, Reader.