东莞市国外网站建设多少钱,莱州人才网,wordpress dnsprefetch,淮安谁家做网站1049: [HAOI2006]数字序列 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1813 Solved: 789[Submit][Status][Discuss]Description 现在我们有一个长度为n的整数序列A。但是它太不好看了#xff0c;于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数也不希望改变的幅度太大。 Input 第一行包含一个数n接下来n个整数按顺序描述每一项的键值。n35000,保证所有数列是随机的 Output 第一行一个整数表示最少需要改变多少个数。 第二行一个整数表示在改变的数最少的情况下每个数改变的绝对值之和的最小值。 Sample Input 4 5 2 3 5 Sample Output 1 4 被细节恶心到啦。第一问可以补集转换减下标然后求最长不下降子序列用总序列长度-lis长度水过关键是这个第二问呐。。有个并不显然的显然结论若jif[j]1f[i]a[j]a[i](保证j可以转移到i)那么把这段区间中的数值改成a[j]或者a[i]一定是最优的跑个dp决策 这里有证明http://pan.baidu.com/share/link?uk2651016602shareid1490516411 1 #includebits/stdc.h2 #define ll long long3 #define N 350054 using namespace std;5 int n,mx,a[N],b[N],f[N],hd[N],nxt[N];ll g[N],s1[N],s2[N];6 int find(int x){7 int l1,rmx,mid,ans0;8 while(lr){9 if(b[mid(lr)1]x)l(ansmid)1;
10 else rmid-1;
11 }return ans;
12 }
13 void dp(){
14 memset(b,0x3f,sizeof(b));
15 b[0]-130;
16 for(int i1;in;i){
17 int pfind(a[i]);
18 mxmax(mx,f[i]p1);
19 b[p1]min(b[p1],a[i]);
20 }
21 }
22 void add(int x,int y){nxt[y]hd[x];hd[x]y;}
23 void solve(){
24 //memset(g,0x3f,sizeof(g));g[0]0;
25 for(int i1;in;i)g[i]1ll60;
26 memset(hd,-1,sizeof(hd));
27 for(int in;i0;i--)add(f[i],i);
28 for(int i1;in;i){
29 for(int jhd[f[i]-1];~jji;jnxt[j]){
30 if(a[j]a[i])continue;
31 for(int kj;ki;k)
32 s1[k]abs(a[k]-a[j]),s2[k]abs(a[k]-a[i]);
33 for(int kj1;ki;k)
34 s1[k]s1[k-1],s2[k]s2[k-1];
35 for(int kj;ki;k)
36 g[i]min(g[i],g[j]s1[k]-s1[j]s2[i]-s2[k]);
37 }
38 }
39 }
40 int main(){
41 scanf(%d,n);a[0]-130;
42 for(int i1;in;i)
43 scanf(%d,a[i]),a[i]-i;
44 a[n]130;
45 dp();solve();
46 printf(%d\n%lld\n,n-mx,g[n]);
47 return 0;
48 } 转载于:https://www.cnblogs.com/wsy01/p/8324600.html
