hdu5256|hdu5256 序列变换 dp LIS hdu5256序列变换dpLIS

【hdu5256|hdu5256 序列变换 dp LIS】点击打开链接
思路：
lis的变形，唯一不同的是条件a[i] - i > a[j] - j + 1,i>j。因为要确保这两个元素之间能插入i - j + 1个元素

每个数先减去它的下标，防止下面的情况发生：加入序列是1,2,2,2,3,这样求上升子序列是3，也就是要修改2个，但是中间的两个2，变化范围又不能超过（1,3）那么这样求的也就不对，但是减掉之后，相当于给中间重复的数留下了修改的空间解释下为什么可以减而保持正确性：因为题目所求时严格递增，假设是2，3, 4，那么变成1, 1, 1，所以在LIS里非严格递增就可以了这也是为什么要在upper_bound的位置插入另外：lower_bound返回第一个>=key的位置；upper_bound返回第一个>key的位置，这样相减才是key的个数

求严格递增的LIS的方法(非严格递增的LIS只要把lower_bound改成upper_bound)

1 memset(b,0x3f,sizeof(b)); 2 int mx = -1; 3 for(int i=1; i<=n; i++){ 4int pos = lower_bound(b+1,b+1+n,a[i])-b; 5b[pos] = a[i]; 6mx = max(mx,pos); 7 }

代码：

1 #include 2 using namespace std; 3 4 const int maxn = 1e5+10; 5 6 int n,a[maxn],b[maxn]; 7 8 // int dp(){ 9 //int len=1; 10 //b[1] = a[1]; 11 //for(int i=2; i<=n; i++){ 12 //if(a[i]>=b[len]){ 13 //len++; 14 //b[len] = a[i]; 15 //}else{ 16 //int pos = upper_bound(b+1,b+len,a[i])-b; 17 //b[pos] = a[i]; 18 //} 19 //} 20 //return len; 21 // } 22 23 int main(){ 24int T; scanf("%d",&T); 25for(int cas=1; cas<=T; cas++){ 26scanf("%d",&n); 27for(int i=1; i<=n; i++){ 28scanf("%d",&a[i]); 29a[i] -= i; 30} 31 32memset(b,0x3f,sizeof(b)); 33int mx = -1; 34for(int i=1; i<=n; i++){ 35int pos = upper_bound(b+1,b+1+n,a[i])-b; 36b[pos] = a[i]; 37mx = max(mx,pos); 38} 39 40int ans = n-mx; 41printf("Case #%d:\n%d\n",cas,ans); 42 43// int ans = n-dp(); 44// printf("Case #%d:\n%d\n",cas,ans); 45} 46 }

转载于:https://www.cnblogs.com/yxg123123/p/6827727.html