CodeforcesRound#261(Div.2)[ABCDE]

分析：
很明显：
1. f(1, i, a[i])就是指a[i]前面包括a[i]的数中，有几个值=a[i]。
2. f(j, n, a[j])就是指a[j]后面包括a[j]的数中有几个值=a[j]。

虽然a[x]范围不小，但是n的范围是1000，不是很大，所以我们可以用map预处理出f(1, i, a[i])和f(j, n, a[j])，记为s1[n], s2[n]。

这样就变成求满足s1[i] > s[j]， i < j情况的数量了,你会发现跟求逆序对一样了。这时就可以用线段树或树状数组求逆序数对的方法解决这个问题了。不懂线段树怎么解的可以看：HDU 1394 Minimum Inversion Number（线段树求最小逆序数对）。

代码：

/*
*  Author:      illuz 
*  File:        D.cpp
*  Create Date: 2014-08-16 00:18:08
*  Descripton:   
*/

#include 
#include 
#include 
#include 
#include 

E - Pashmak and Graph

题意：
给出一个有向带权值的图，要求出最长递增链路的长度。也就是当前边的权值要大于前一条边的。

分析：
刚开始写了个搜索+map记忆化，然后就TLE了QvQ...
其实可以用数组的dp来做，先对边从小到大排序，从小到达处理，对于相同的一类边，进行对边dp，然后更新对点dp。

@barty巨巨：

将所有边按边权从小到大排序，顺序扫描，如果没有重复边权的话，对于(u, v, d)这条有向边，可以直接用之前求的到u点的最长路径+1来更新到v的最长路径。
不过题目中没有保证所有边权不同，为了保证严格递增，所以对于相同边权需要做一个缓冲处理。

代码：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        E.cpp
*  Create Date: 2014-08-16 09:43:59
*  Descripton:   
*/

#include 
#include 
#include 
#include 
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)

const int N = 3e5 + 10;

struct Edge {
	int x;
	int y;
	int w;
	bool operator <(const Edge& e) const {
		return w < e.w;
	}
} e[N];

int n, m;
int edge[N], node[N];		// edges and nodes' dp

int main() {
	while (~scanf("%d%d", &n, &m)) {
		memset(edge, 0, sizeof(edge));
		memset(node, 0, sizeof(node));

		repf (i, 1, m) {
			scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
		}

		sort(e + 1, e + m + 1);

		repf (i, 1, m) {
			int j = i;
			while (j <= m && e[i].w == e[j].w) {		// update edges' dp
				int x = e[j].x;
				edge[j] = max(edge[j], node[x] + 1);
				j++;
			}

			j = i;
			while (j <= m && e[i].w == e[j].w) {		// update nodes' dp
				int y = e[j].y;
				node[y] = max(edge[j], node[y]);
				j++;
			}
			i = j - 1;
		}

		int ans = 0;
		repf (i, 1, m)
			ans = max(ans, edge[i]);

		printf("%d\n", ans);
	}
	return 0;
}