#include<bits/stdc++.h> using namespace std; int n,m,a[1001],f[500][500],mi[500][500],i,j; int main() { cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; for(i=1;i<=n;i++) for(j=1;j<=m;j++) f[i][j]=9999999;//赋为最大值 for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) mi[i][j]=mi[i][j-1]+a[j]-a[(i+j)/2];//从第i个村庄到第j个村庄中只建一个邮局的总路径长度 f[i][1]=mi[1][i];//转移到f } for(i=2;i<=n;i++) for(j=2;j<=m;j++) for(int k=j-1;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+mi[k+1][i]); cout<<f[n][m]<<endl; return 0; }
#include<iostream> #include<cstring> using namespace std; const int N = 1050; int a[N],f[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++)f[i]=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(a[j]<a[i])f[i]=max(f[i],f[j]+1); } } int ans = 1; for(int i=0;i<n;i++)ans = max(ans,f[i]); cout<<ans<<endl; return 0; }
原文:https://www.cnblogs.com/yun-an/p/11477893.html