题意繁琐, 不想写了......还是自己看题去吧...
最后我是简化为求一个DAG图的最长路径, 用dfs+剪枝+记忆化搜索dp来完成
本题一共有223个测试数据, 本来第222个test本地运行之后崩掉了...dfs的太深, 栈溢出了orz, 可是提交上oj之后却是AC. 果然LINUX博大精深我不懂啊233
有需要第222个test的或者是要所有数据的可以私信...
学长建议我用bfs+topo序做, 下次试试吧...一开始写了个bfs的也是本地崩了然后重写了dfs... 不知道之前的那个程序能不能过呢
这题光是读题就花了很久, 没有题解而且卡题的时候感觉整个人都不好了orz, 特别想砸电脑....不过这也是一种锻炼吧, 毕竟只是08年日本队伍冬合宿的某一天的题而已, 一想到他们每天都要做6题这个难度的我就觉得自己弱爆了....
看到四五年前的几个老怪物写的似乎都比我短而且内存占用少... 不过效率上的话这个还是最快的^_^
就内存问题而言, 第一次AC我烧了51+兆内存...在next数组那里我开了100...事实上如果用正确的建图方法, 只要开3就行了
这样内存占用一口气降到了8M, 必须吸取教训→_→
/*author: birdstorm*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <climits>#define