重新学习dp的第一步,计划学习dp用时40个学时,砥砺前行吧大伙
1 //最长上升子序列问题 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int N=1e5+10; 5 int f[N],a[N],n,res; 6 int main() 7 { 8 cin>>n; 9 for(int i=0;i<n;i++) cin>>a[i]; 10 for(int i=0;i<n;i++) 11 { 12 f[i]=1; 13 for(int j=0;j<i;j++) 14 if(a[i]>a[j]) 15 f[i]=max(f[i],f[j]+1); 16 } 17 for(int i=0;i<n;i++) res=max(res,f[i]); 18 cout<<res; 19 return 0; 20 } 21 //最长上升子序列优化 22 //基于贪心做法 23 //首先可以证明整个f数组是单调递增的，即对于任意的索引i < j，都有 f[i] < f[j]。反证法如下： 24 //若f[i] == f[j]，对于f[j]对应的长度为j的最长上升子序列，其倒数第2个元素值一定小于f[j]，那么这个倒数第2个元素值可以作为f[i]，则有f[i] < f[j]。 25 //同理可证f[i] > f[j]的情形。 26 //继续分析： 27 //如已扫描序列1 4 2 3，根据我们的定义，有f[3] = 3（序列1 2 3的尾元素），再往后扫描时，如果是4，即序列为1 4 2 3 4时，就可以根据f[3] = 3（3 < 4）往后延长一个LIS长度（即f长度变为4），而且使得f[4] = 4（即1 2 3 4的尾元素）。这样显然是合理的，而且可以为以后LIS长度的更新以及尾元素的更新做铺垫。 28 // 或者从反面考虑：如果我们f[i]存储的不是长度为i的最长上升子序列的尾元素，如f[3] = 5（存1 4 5的尾元素），那么扫描后续元素就无法最大化地延长上升序列，无法达到题目要求。 29 // 注意在思考问题时，从集合的角度考虑问题，即每个f[i]首先是关于所有长度为i的上升序列的函数，其次，f[i]存的是这些上升序列尾元素的最小值。 30 // 那么在扫描原数组的时候，对于第i个数，可以根据前i-1个数得到的f数组的结果，对f数组进行长度或内容的更新，具体表现如下：（设f数组的实际长度为cnt） 31 // 1、若a[i] > f[cnt]，则对于从1至cnt的f中的每一个f[j]，都有a[i] > f[j]（因为前面已经证明f单调递增）。那么当前的a[i]可以作为长度为cnt+1的上升子序列的最小元素（因为当前只有这么一个长度为cnt+1的上升序列），即f[cnt+1] = a[i]，同时cnt++. 32 // 2、若a[i] <= f[cnt]，则无法使得上升序列变长，因为f[cnt]是长度为cnt的所有上升序列尾元素的最小值。因此，它的作用是，更新对应的一个f。显然，对于从后往前第一个小于a[i]的f[j]而言，a[i]可以接到f[j]所代表的那个最优上升序列后面，从而更新f[j+1]（长度为j+1的上升序列的尾元素最小值）。因为从刚才的叙述可以知道，原f[j+1] >= a[i]。故这样a[i]的作用是直接改变f的一个恰当元素值，同时为最终cnt的更新作准备（通过将一个f的元素值变小，使得后面元素接到前面更具有可能）。 33 #include<bits/stdc++.h> 34 using namespace std; 35 const int N=1e5+10; 36 int n,m,k,res,f[N],q[N],a[N]; 37 int main() 38 { 39 cin>>n; 40 for(int i=0;i<n;i++) cin>>a[i]; 41 q[0]=-2e9; 42 for(int i=0;i<n;i++) 43 { 44 if(q[res]<a[i]) q[++res]=a[i]; 45 else{ 46 int l=0,r=res; 47 while(l<=r){ 48 int mid=l+r>>1; 49 if(q[mid]>=a[i]) r=mid-1; 50 else l=mid+1; 51 } 52 q[l]=a[i]; 53 } 54 } 55 cout<<res; 56 return 0; 57 } 58 //最长上升子序列合 59 //f[i]是第i位的最大上升子序列合,设k为倒数第二位的话 60 //那f[i]=f[k]+a[i],以此类推 61 #include<bits/stdc++.h> 62 using namespace std; 63 const int N=1e5+10; 64 int n,res,a[N],f[N]; 65 int main() 66 { 67 cin>>n; 68 for(int i=0;i<n;i++) cin>>a[i]; 69 for(int i=0;i<n;i++) 70 { 71 f[i]=a[i]; 72 for(int j=0;j<i;j++) 73 if(a[i]>a[j]) f[i]=max(f[i],f[j]+a[i]); 74 } 75 for(int i=0;i<n;i++) res=max(res,f[i]); 76 cout<<res; 77 return 0; 78 } 79 //怪盗基德滑翔翼 80 #include<bits/stdc++.h> 81 using namespace std; 82 const int N=1e5+10; 83 int n,res,a[N],q[N],len; 84 int main() 85 { 86 cin>>n; 87 q[0]=-2e9; 88 for(int i=0;i<n;i++) cin>>a[i]; 89 for(int i=0;i<n;i++) 90 { 91 if(q[len]<a[i]) q[++len]=a[i]; 92 else{ 93 int l=0,r=n-1; 94 while(l<=r){ 95 int mid=l+r>>1; 96 if(q[mid]>=a[i]) r=mid-1; 97 else l=mid+1; 98 } 99 q[l]=a[i]; 100 } 101 } 102 res=len,len=0; 103 memset(q,0,sizeof q); 104 q[0]=2e9; 105 for(int i=n-1;i>=0;i--) 106 { 107 if(q[len]<a[i]) q[++len]=a[i]; 108 else{ 109 int l=0,r=n-1; 110 while(l<=r){ 111 int mid=l+r>>1; 112 if(q[mid]>=a[i]) r=mid-1; 113 else l=mid+1; 114 } 115 q[l]=a[i]; 116 } 117 } 118 cout<<max(res,len)<<endl; 119 return 0; 120 } 121 //登山,合唱队形:https://www.luogu.com.cn/problem/P1091 122 #include<bits/stdc++.h> 123 using namespace std; 124 const int N=1e5+10; 125 int f[N],g[N],n,m,res,a[N],t,q[N]; 126 int main() 127 { 128 cin>>n; 129 for(int i=0;i<n;i++) cin>>a[i]; 130 for(int i=0;i<n;i++) 131 { 132 f[i]=1; 133 for(int j=0;j<i;j++) 134 if(a[i]>a[j]) f[i]=max(f[i],f[j]+1); 135 } 136 for(int i=n-1;i>=0;i--) 137 { 138 g[i]=1; 139 for(int j=n-1;j>=i;j--) 140 if(a[i]>a[j]) g[i]=max(g[i],g[j]+1); 141 } 142 for(int i=0;i<n;i++) res=max(res,g[i]+f[i]-1); 143 cout<<res;//登山 144 cout<<n-res;//合唱队行 145 return 0; 146 } 147 //友好城市:https://www.luogu.com.cn/problem/P2782 148 //只需要对y从城市排序,然后求x的最长上升子序列就可以 149 #include<bits/stdc++.h> 150 using namespace std; 151 const int N=2e5+10; 152 int x,n,res,len=0,q[N],f[N]; 153 struct node 154 { 155 int x,y; 156 bool operator<(const node&w)const 157 { 158 return y<w.y; 159 } 160 }city[N]; 161 int main() 162 { 163 cin>>n; 164 for(int i=0;i<n;i++) cin>>city[i].x>>city[i].y; 165 sort(city,city+n); 166 q[0]=-2e9; 167 for(int i=0;i<n;i++) 168 { 169 if(q[len]<city[i].x) q[++len]=city[i].x; 170 else{ 171 int l=0,r=len; 172 while(l<=r){ 173 int mid=l+r>>1; 174 if(q[mid]>=city[i].x) r=mid-1; 175 else l=mid+1; 176 } 177 q[l]=city[i].x; 178 } 179 } 180 cout<<len; 181 return 0; 182 }