HDU 4719 Oh My Holy FFF

N soldiers from the famous "*FFF* army" is standing in a line, from left to right. 

o o o o o o o o o o o o o o o o o o

/F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\

/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \

You, as the captain of *FFF*, want to divide them into smaller groups, but each group should still be continous in the original line. Like this: 

o o o | o o o o | o o o o o o | o o o o o

/F\ /F\ /F\ | /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\

/ \ / \ / \ | / \ / \ / \ / \ | / \ / \ / \ / \ / \ / \ | / \ / \ / \ / \ / \

In your opinion, the number of soldiers in each group should be no more than L. 

Meanwhile, you want your division be "holy". Since the soldier may have different heights, you decide that for each group except the first one, its last soldier(which is the rightmost one) should be strictly taller than the previous group's last soldier. That is, if we set bi as the height of the last soldier in group i. Then for i >= 2, there should be b 

i > b 

i-1. 

You give your division a score, which is calculated as 

, b 

0 = 0 and 1 <= k <= M, if there are M groups in total. Note that M can equal to 1. 

Given the heights of all soldiers, please tell us the best score you can get, or declare the division as impossible.

Input

The first line has a number T (T <= 10) , indicating the number of test cases. 

For each test case, first line has two numbers N and L (1 <= L <= N <= 10 

5), as described above. 

Then comes a single line with N numbers, from H1 to Hn, they are the height of each soldier in the line, from left to right. (1 <= H 

i <= 10 

5)

Output

For test case X, output "Case #X: " first, then output the best score.

Sample Input

2

5 2

1 4 3 2 5

5 2

5 4 3 2 1

Sample Output

Case #1: 31

Case #2: No solution

其实就是一个线性的dp,但是需要考虑到前L个比当前小的最大值，所以通过线段树优化。

线段树中保存权值区间的最大值，单点更新，同时在底层维护一个set，来存放权值相同的不同答案。

#include<map>   
#include<set>  
#include<ctime>    
#include<cmath>   
#include<stack>
#include<queue>     
#include<string>    
#include<vector>    
#include<cstdio>        
#include<cstring>      
#include<iostream>    
#include<algorithm>        
#include<functional>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))        
#define rep(i,j,k) for(int i=j;i<=k;i++)        
#define per(i,j,k) for(int i=j;i>=k;i--)        
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])        
#define inone(x) scanf("%d",&x)        
#define intwo(x,y) scanf("%d%d",&x,&y)        
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)      
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)     
#define lson x<<1,l,mid    
#define rson x<<1|1,mid+1,r    
#define mp(i,j) make_pair(i,j)    
#define ff first    
#define ss second    
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const int M = 1e5;
const double eps = 1e-8;
int T, n, m, cas = 1;
int a[N];
LL f[N], g[N];
multiset<LL> p[N];

void clear(int x, int l, int r)
{
  f[x] = 0;
  if (l == r) {
    p[r].clear(); return;
  }
  int mid = l + r >> 1;
  clear(lson); clear(rson);
}

void insert(int x, int l, int r, int u, LL v)
{
  if (l == r) { 
    p[r].insert(v); 
    multiset<LL> ::iterator i = p[r].end();
    f[x] = *(--i);
    return; 
  }
  int mid = l + r >> 1;
  if (u <= mid) insert(lson, u, v);
  else insert(rson, u, v);
  f[x] = max(f[x << 1], f[x << 1 | 1]);
}

void del(int x, int l, int r, int u, LL v)
{
  if (l == r) {
    p[r].erase(p[r].find(v));
    if (p[r].size())
    {
      multiset<LL> ::iterator i = p[r].end();
      f[x] = *(--i);
    }
    else f[x] = 0;
    return;
  }
  int mid = l + r >> 1;
  if (u <= mid) del(lson, u, v);
  else del(rson, u, v);
  f[x] = max(f[x << 1], f[x << 1 | 1]);
}

LL find(int x, int l, int r, int u)
{
  if (r <= u) return f[x];
  int mid = l + r >> 1;
  LL now = find(lson, u);
  if (mid < u) now = max(now, find(rson, u));
  return now;
}

int main()
{
  for (inone(T); T--; cas++)
  {
    intwo(n, m);
    rep(i, 1, n) inone(a[i]);
    clear(1, 0, M);
    g[0] = 1; a[0] = 0;
    insert(1, 0, M, a[0], g[0]);
    rep(i, 1, n)
    {
      g[i] = find(1, 0, M, a[i] - 1);
      if (g[i])
      {
        g[i] = g[i] + 1LL * a[i] * (a[i] - 1);
        insert(1, 0, M, a[i], g[i]);
      }
      if (i >= m && g[i - m]) del(1, 0, M, a[i - m], g[i - m]);
    }
    if (g[n]) printf("Case #%d: %lld\n", cas, g[n] + a[n] - 1);
    else printf("Case #%d: No solution\n", cas);
  }
  return 0;
}