HDU5773多用途零的动态规划与贪心算法

### 问题描述
给定一个整数序列，允许将序列中的所有0替换为任意整数（包括正数和负数），任务是计算该序列的最大递增子序列（LIS）的长度。

### 解决方案
此问题可以通过结合动态规划和贪心策略来有效解决。首先，我们考虑将所有0从原始序列中移除，并计算剩余元素构成的最长递增子序列的长度。这一步骤处理的是0位于潜在递增子序列外部的情形。

然而，当0出现在递增子序列内部时，解决方案需要进行调整。具体而言，在遍历输入序列时，对于每个非0元素，将其值减少其之前出现的0的数量。例如，对于序列1, 2, 0, 3, 4，经过转换后的序列为1, 2, 2, 3。接下来，计算这个新序列的LIS长度，并将结果加上原序列中0的总数，即得到最终答案。

这种方法巧妙地利用了贪心策略，确保了即使0作为可变元素存在，也能准确计算出最大递增子序列的长度。

### 代码实现
```cpp
#include
using namespace std;
int ks = 0, T, n, a[100005];
int main(){
scanf("%d", &T);
while(T--){
memset(a, 0, sizeof(a));
int m = 0;
int tot = 0;
scanf("%d", &n);
for(int i = 0; i int x;
scanf("%d", &x);
if(x == 0) tot++;
else {
x -= tot;
int p = lower_bound(a, a + m, x) - a;
a[p] = x;
m = max(m, p + 1);
}
}
printf("Case #%d: %d\n", ++ks, m + tot);
}
return 0;
}
```
上述代码实现了上述逻辑，通过动态规划和贪心策略有效地解决了问题。