8382: BZOJ4382:[POI2015]Podzial naszyjnika
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
长度为n的一串项链,每颗珠子是k种颜色之一。 第i颗与第i-1,i+1颗珠子相邻,第n颗与第1颗也相邻。
切两刀,把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。
求方案数量(保证至少存在一种),以及切成的两段长度之差绝对值的最小值。
输入格式
第一行n,k(2<=k<=n<=1000000)。颜色从1到k标号。
接下来n个数,按顺序表示每颗珠子的颜色。(保证k种颜色各出现至少一次)。
输出格式
一行两个整数:方案数量,和长度差的最小值
样例输入
9 5 2 5 3 2 2 4 1 1 3
样例输出
4 3
提示
四种方法中较短的一条分别是(5),(4),(1,1),(4,1,1)。相差最小值6-3=3。
题目来源
鸣谢Claris