诸神的棋盘dp全攻略,da和dp的区别

饥饿的WZK 题目大意 就是有N个区间，每个区间的长度不一样，但又可能和其它区间重叠. 问最大的区间长度. 输入样例 31 37 83 4 输出样例 5 解题思路 其实这道题就是一道DP，看是否重叠，如果重叠那就判断是否要用即可. 程序如下 #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,f[10001],ans;struct jgt{int x,y,sum,last;}a[10001];bool cmp(jgt x,jgt y){return x.y<y.y;}int main(){freopen("hunger.in","r",stdin);freopen("hunger.out","w",stdout);scanf("%d",&n);ans=n;for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y),a[i].sum=a[i].y-a[i].x+1;//区间长度sort(a+1,a+1+n,cmp);//排序for(int i=1;i<=n;++i){for(int j=i-1;j>=0;--j){if(a[j].y<a[i].x) //看是否重叠{f[i]=max(f[i-1],f[j]+a[i].sum);//最优的break;}}} printf("%d",f[n]);return 0;}