问题简介

具体参照 hihocoder官网。

实现思路

最长连续提交天数等价于相邻未提交日期差值的最大值-1，所以原问题是求解去除哪些日期之后可以使得相邻日期的差值最大。 那么消除的日期必定是相邻的日期，否则可以通过改变某个不相邻日期为相邻日期使得差值增大。处理的时候前后加入虚拟日期第0日以及第101日，方便边界的处理。

代码

#include <iostream> using namespace std; int main() { int T; cin >> T; int n,m,nums[102]; nums[0] = 0; int result; for (int t = 0;t < T;++t){ cin >> n >> m; ++n; for (int i = 1;i < n;++i) cin >> nums[i]; nums[n] = 101; --n; if (m >= n) cout << 100 << endl; else { result = 0; for (int i = 0;i < n-m;++i){ if (result < nums[i+m+1]-nums[i]-1) result = nums[i+m+1]-nums[i]-1; } cout << result << endl; } } return 0; }

后记：错误的思路

想要减少枚举的次数，维护两端索引值，然后从中间包括n个日期到m个日期递减。（后来发现并没有丝毫的进步，都是n-m） 这里的递归默认的“有m个补提交卡去除的日期必定包含在有m+1个补提交卡去除的日期中”是错误的。反例是20 21 90，当m=1去除90，当m=2去除20&21. 发现反例的脚本代码可以参照 [hihocoder1039]字符消除