我一开始想的是前i个区间的最大值
显然对于当前的区间，有不选和选两种情况
如果不选的话，就继承f[i-1]
如果选的话，找离当前区间最近的区间取最优
f[i] = max(f[i-1, f[j] + a[i].v()) j为i前面区间中能取得离i最近的区间
那么显然这里涉及到f[i]的时候取的最后一个区间是什么，才能比较
那么就要额外开一个last数组来记录
最后输出f[n]
这样写很麻烦，但是我还是强行写出然后还AC了
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
int f[MAXN], last[MAXN], n;
struct node
{int l, r;int v() { return r - l + 1; }bool operator < (const node& rhs) const{return r < rhs.r || (r == rhs.r && l < rhs.l); }
}a[MAXN];int main()
{scanf("%d", &n);REP(i, 1, n + 1) scanf("%d%d", &a[i].l, &a[i].r);sort(a + 1, a + n + 1);f[1] = a[1].v();last[1] = a[1].r;REP(i, 2, n + 1){if(a[i].v() > f[i-1]){f[i] = a[i].v();last[i] = a[i].r;}else{ f[i] = f[i-1];last[i] = last[i-1];}for(int j = i - 1; j >= 1; j--)if(last[j] < a[i].l){if(f[i] < f[j] + a[i].v()){f[i] = f[j] + a[i].v();last[i] = a[i].r;}break;}}printf("%d\n", f[n]);return 0;
}然后我就突然想到
如果我们换一下状态，设f[i]为以i为结尾的区间的最大值，也就是说i区间必须要取
那么这个时候岂不是f[i]的最后一个区间就是a[i]，不就可以省去一个last数组了吗
同时答案不是f[n]，而是f数组里面的最大值，因为答案不一定以n为结尾。
然后就写了，代码大大简化，爽！
所以有时候还是要想一个合适的状态，可以大大简化程序和思维量
最后其实按照题目可以设置数据n=1，这个时候我的程序会输出0，会错。
但是数据里面没有这个坑……有的话特判一下就好了
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
int f[MAXN], n;
struct node
{int l, r;int v() { return r - l + 1; }bool operator < (const node& rhs) const{return r < rhs.r || (r == rhs.r && l < rhs.l); //对于这道题而言，按照左端 } //点和右端点排序都是对的
}a[MAXN];int main()
{scanf("%d", &n);REP(i, 1, n + 1) scanf("%d%d", &a[i].l, &a[i].r);sort(a + 1, a + n + 1);int ans = 0;REP(i, 1, n + 1){f[i] = a[i].v(); //这句话不能省，当前区间先取了再说 REP(j, 1, i)if(a[j].r < a[i].l)f[i] = max(f[i], f[j] + a[i].v());ans = max(ans, f[i]);}printf("%d\n", ans);return 0;
}