首页 > 代码库 > 拦截导弹；合唱队形；友好城市——基本的单调序列动态规划吧
拦截导弹；合唱队形；友好城市——基本的单调序列动态规划吧
合集，三个题目基本上都一样。耗时也不贴了。
拦截导弹：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=128; 5 int n=1,val[N]; 6 int up[N],dn[N],cnt1,cnt2; 7 int main(){ 8 for(int i=0;i<N;i++)up[i]=dn[i]=1; 9 while(cin>>val[n])n++;n--;10 11 for(int i=1;i<=n;i++)12 for(int j=1;j<=i;j++){13 if(val[i]>val[j])up[i]=max(up[i],up[j]+1);14 if(val[i]<val[j])dn[i]=max(dn[i],dn[j]+1);15 cnt1=max(dn[i],cnt1);16 cnt2=max(up[i],cnt2);17 }18 19 cout<<cnt1<<endl<<cnt2<<endl;20 return 0;21 }
合唱队形：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=128; 5 int n,val[N]; 6 int lf[N],rf[N],ans; 7 int main(){ 8 for(int i=0;i<N;i++)lf[i]=rf[i]=1; 9 cin>>n;10 for(int i=1;i<=n;i++)cin>>val[i];11 12 for(int i=2;i<=n;i++)13 for(int j=1;j<i;j++)14 if(val[i]>val[j])15 lf[i]=max(lf[i],lf[j]+1);16 for(int i=n-1;i>=1;i--)17 for(int j=n;j>i;j--)18 if(val[i]>val[j])19 rf[i]=max(rf[i],rf[j]+1);20 21 for(int i=0;i<=n+1;i++)ans=max(ans,lf[i]+rf[i]-1);22 cout<<n-ans<<endl;23 return 0;24 }
友好城市：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 using namespace std; 5 const int N=10086; 6 struct node{ 7 int x,y; 8 bool operator < (const node oth) const {return x<oth.x;} 9 }p[N];10 int n,f[N],res;11 int main(){12 for(int i=0;i<N;i++)f[i]=1;13 cin>>n;14 for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;15 sort(p+1,p+1+n);16 17 for(int i=2;i<=n;i++)18 for(int j=1;j<i;j++)19 if(p[i].y>p[j].y)20 f[i]=max(f[i],f[j]+1);21 22 for(int i=1;i<=n;i++)res=max(res,f[i]);23 cout<<res<<endl;24 return 0;25 }
拦截导弹；合唱队形；友好城市——基本的单调序列动态规划吧
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。