http://codeforces.com/contest/675/problem/E
题目大意：有n个车站，每个车站只能买一张票，这张票能从i+1到a[i]。定义p[i][j]为从i到j所需要买的最小票数。问sigma（p）的和是多少。
思路:感觉我的dp定义能力还是太弱了啊，我刚开始还定义成dp[i]表示1~i-1到i所需要的最小花费和，后来发现这样子我转移不了啊！！
于是重新定义dp[i]表示从i出发到i+1~n所需要的最小票数，然后这样定义就能很好的解决问题啦。然后我们每次贪心的选取j = i+1~a[i]中的a[j]跑的最远的那个，然后进行转移就好了，具体的用线段树维护一下区间吧。
TAT感觉是不难的题目
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") const int maxn = 1e5 + 5; int a[maxn]; int n; struct Tree{ int lpos, rpos; Tree(int l = 0, int r = 0): lpos(l), rpos(r){} }tree[maxn << 2]; inline void push_up(int o){ int lb = o << 1, rb = o << 1 | 1; tree[o].rpos = max(tree[lb].rpos, tree[rb].rpos); if (tree[lb].rpos >= tree[rb].rpos) { tree[o].lpos = tree[lb].lpos; } else tree[o].lpos = tree[rb].lpos; } void build_tree(int l, int r, int o){ if (l == r){ tree[o].rpos = a[l]; tree[o].lpos = l; return ; } int mid = (l + r) / 2; if (l <= mid) build_tree(l, mid, o << 1); if (r > mid) build_tree(mid + 1, r, o << 1 | 1); push_up(o); } Tree query(int l ,int r, int ql, int qr, int o){ if (ql <= l && qr >= r){ return tree[o]; } Tree ans, re; ans.lpos = re.lpos = ans.rpos = re.rpos = 0; int mid = (l + r) / 2; if (ql <= mid) ans = query(l, mid, ql, qr, o << 1); if (qr > mid) re = query(mid + 1, r, ql, qr, o << 1 | 1); if (ans.rpos < re.rpos) ans = re; return ans; } LL dp[maxn];///定义从i开始走到n所需要的最小花费 int main(){ scanf("%d", &n); a[n] = n; for (int i = 1; i <= n - 1; i++) scanf("%d", a + i); memset(tree, 0, sizeof(tree)); build_tree(1, n, 1); LL ans = 0; for (int i = n - 1; i > 0; i--){ Tree pos = query(1, n, i + 1, a[i], 1); dp[i] = n - i + dp[pos.lpos] - (a[i] - pos.lpos); ans += 1LL * dp[i]; } printf("%lld ", ans); return 0; }