宽搜的裸题啊。@KD35OKC 弄起来啊！！！！

第一行：一个实数A
第二行：一个实数B

没调交上去就A了。。。。。。。感觉好爽

输入问题搞了半天……用getline的尝试失败了……

回复 @高高高高高 :
是的，懒得搞正向程序了……

回复 @cstdio : 数据好坑，如果无解会输出不能涂色的点中行数最大的

本题直接枚举会很快，但是用DP写的话，有助于理解DP。

交上去就出错→_→
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void)
{
int ans, day[13] = {0, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}, i, j, k, n, num[366];
freopen("heavven.in", "r", stdin);
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d%d", &j, &k);
num[i] = day[j] + k;
}
fclose(stdin);
sort(num, num + n);
ans = 365 - num[n - 1];
for (; n > 0; --n)
{
i = num[n] - num[n - 1] - 1;
ans = ans > i ? ans: i;
}
freopen("heaven.out", "w", stdout);
printf("%d\n", (ans * 86400 + 184) / 366);
fclose(stdout);
return 0;
}

此题稍加改动即为“Fixed Partition Memory Management”

第二问最上升子序列

如图所示，如何统计不相交下降序列(元素不相交)的个数呢。
我们只需从最靠左下的序列出发，可知，若要找下一个上升元素，不可能存在于改元素所在的不上升序列中。
故最长上升序列就为不上升序列的个数。

回复 @CH.Genius_King :
good!

so easy!

数据淼

回复 @CSY.Girl_Queen :
对于一个问题而言，存在某种贪心策略可得到局部最优解。
但是若证明该贪心策略所得到的局部最优解亦是全局最优解仍需严格的证明过程。
在这里，我误认为三集合就可以表示所有的状态，但是存在以下问题：
1。集合$ABC$都代表着在全局中始终为最优解的集合。却无法确定集合的合并方式。
2.无法确定先选取哪个集合为B进行合并$(A(BCD)),((ABC)D)$

挂了N次。。。

回复 @CH.Genius_King :
我将反例用统一的形式表示，可表示为4种状态的情况。
设状态集合$A,B,C,D$，形式可以包含多种决策，但他们在形式上是统一的。
形式1双双合并再合并
$F(ABCD)=W(A)+W(B)+W(C)+W(D)+W(AB)+W(CD)$
形式2逐次相邻合并型
$F(ABCD)=W(A)+W(B)+W(AB)+W(C)+W(ABC)+W(D)$
形式1$δ(ABCD)=W(D)$
形式2$δ(ABCD)=W(AB)$

然后我就无意间又证明贪心算法是对的！

我们都知道这是一道很基础的DP。
$F$为所需求的状态值，在石子归并问题中理解为权重。$W$为物品重量，$φ$为与参数(状态$K$)相关的状态转移权重。
$F(A)=Min(F(A-K)+φ(K))$类型的动归(A,K表状态集合，在石子归并问题中我们使它内部元素有序)。
在石子归并问题中，我们认为$φ(K)=W(A)+W(A-K)$
可是，如何证明它不可以使用贪心算法呢？
假设有序集合$A,B,C$表示不同的状态。终止状态为$(ABC)$初始价值(状态)则为$Ω(INIT)=F(A)+F(B)+F(C)$
策略1$F(ABC)=W(A)+W(B)+W(AB)+W(ABC)+Ω(INIT)$
策略2$F(ABC)=W(B)+W(C)+W(BC)+W(ABC)+Ω(INIT)$
两式比较取差异部分：
策略1$δ(ABC)=2W(A)$
策略2$δ(ABC)=2W(C)$
此时的可以看出在初末状态相同时，策略1与策略2有明显的优劣。我们只需修改$ABC$集合代表的状态（只需保证其始终为有序态即可），既可以得到全局最优解

这也太快了……

这题目不科学啊……传感器阵列毛线啊……
题中的图是HAARP（我自己加的，原题上没有），估计原题作者看这个看多了……
但是用来监测飞机的雷达真·不这样啊……远程预警雷达是一个一大坨，而不是阵列……

儿童机协会
Association of Children Machines,ACM
笑尿