回顾一些较简单的dp题
两问:一个导弹拦截系统最多能拦多少导弹 要拦截所有导弹至少需要多少拦截系统
第一问感觉是一个比较巧妙的方法:
维护一个单调递减的序列 length[] 记录的是拦截导弹的高度
当下一个导弹小于 length[] 最后一个数(最小的数)则直接把它加在序列后即可
若大于 则找到序列中比它大的最小的数(二分)然后替换 可以保证最优
第二问 就是贪心啊
当现有的导弹系统的拦截高度都小于当前导弹的高度 则开一个新的系统
否则找到拦截高度比导弹高度高的最小的系统来拦截
这里记录系统拦截高度的数组一定是单调递增的无需排序
View Code#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int x; bool f; int height[100010],length[100010],minh[100010]; int main() { int y=1; while(scanf("%d",&height[y])==1) y++;y--; length[1]=height[1]; int top=1; for(int i=2;i<=y;i++) { if(height[i]<=length[top]) length[++top]=height[i]; else { int left=1,right=top,ans; while(left<=right) { int mid=(left+right)/2; if(length[mid]<height[i]) { ans=mid; right=mid-1; } else left=mid+1; } length[ans]=height[i]; } } cout<<top<<endl; int maxa=0; for(int i=1;i<=y;i++) if(maxa<length[i]) maxa=length[i]; int num=1;minh[1]=height[1]; for(int i=2;i<=y;i++) { f=0; for(int j=1;j<=num;j++) if(height[i]<=minh[j]) {minh[j]=height[i];f=1;break;} if(f==0) minh[++num]=height[i]; } cout<<num; return 0; }
区间dp一般套路:枚举起点 枚举区间长度(或终点) 枚举断点 转移
注意枚举的顺序要保证由已知推未知
很多时候遇到环都可能要断环为链(图论也是这样)
View Code1 #include<iostream> 2 using namespace std; 3 int a[210]; 4 int s[210]; 5 int ans1[210][210]; 6 int ans2[210][210]; 7 int main() 8 { 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++) 12 { 13 cin>>a[i]; 14 s[i]=s[i-1]+a[i]; 15 a[i+n]=a[i]; 16 } 17 for(int i=n+1;i<=n*2;i++) 18 s[i]=s[i-1]+a[i]; 19 for(int i=1;i<=2*n;i++) 20 for(int j=1;j<=2*n;j++) 21 if(j!=i) ans2[i][j]=2100000; 22 for(int h=1;h<=n;h++) 23 { 24 for(int i=h+n-1;i>=h;i--) 25 { 26 for(int j=i;j<=h+n-1;j++) 27 { 28 for(int k=i+1;k<=j;k++) 29 { 30 ans1[i][j]=max(ans1[i][j],ans1[i][k-1]+ans1[k][j]+s[j]-s[i-1]); 31 ans2[i][j]=min(ans2[i][j],ans2[i][k-1]+ans2[k][j]+s[j]-s[i-1]); 32 } 33 } 34 } 35 } 36 int maxn,minn=2100000; 37 for(int i=1;i<=n;i++) 38 { 39 maxn=max(maxn,ans1[i][i+n-1]); 40 minn=min(minn,ans2[i][i+n-1]); 41 } 42 cout<<minn<<endl<<maxn<<endl; 43 return 0; 44 }