2015
04-13

# Chocolate Machine

There is a Vending machine sales which sell magic chocolate in Renren office. The chocolate is shaped like a n*m rectangle, and
each 1*1 unit is assigned with a delicious degree. A consumer can chose a Staircase-shaped chocolate (whose bottom and right edge must be a straight line) to buy, if there isn’t
any units’ delicious degree is less than K. And the price of this block is equal to the sum of delicious degree it contains.
Chould you help the manager to figer out how much can he earn at most?

This is a sample of a Staircase-shaped chocolate. Noting that a rectangle is also a Special case of Staircase-shaped
chocolate.

The first line contains a positive integer: the number of test cases, at most 100.
After that per test case:
One line with three integers n, m and K (1 ≤ n, m ≤ 3 000, K ≤ 1000000): the dimensions of chocolate.
Next n lines, each with m positive integers(less than 1000000). The jth colume of the ith line represents the delicious
degree of i*j unit.

1
2 3 2
2 3 4
2 2 1

9
Hint
We can sold:
2 3
2 2
or
2 3 4 

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

const int N = 3005;
typedef long long LL;

LL sum[N][N] ,f[N];
bool a[N][N];

int que[N] , up[2][N];

inline LL get( int lx,int ly,int rx,int ry ){
lx--;ly--;
//cout<<sum[rx][ry]<<" "<<sum[lx][ly]<<" "<<sum[rx][ly]<<" "<<sum[lx][ry]<<endl;
return sum[rx][ry] + sum[lx][ly] - sum[rx][ly]-sum[lx][ry];
}

int main() {
int test, i , j , n , m , k , tmp;
scanf("%d",&test);
while( test-- ) {
scanf("%d%d%d",&n,&m,&k);
memset( sum[0] , 0 ,sizeof( sum[0] ));
for( i = 1; i <= n ;i++) {
sum[i][0] = 0 ;
for( j = 1; j <= m;j++ ) {
scanf("%d",&tmp);
a[i][j] = ( tmp >= k );
//cout<<i<<" "<<j<<" "<<sum[i][j]<<endl;
}
}
memset( up , 0 ,sizeof( up ));
LL ans = 0;
for( i = 1; i <= n;i++ ) {
int cur = i%2;
int head = 0 ,tail = 0;
memset( f , 0 ,sizeof( f ));
if( a[i][1] ) {
up[cur][1] = up[1-cur][1] + 1;
f[1] = get( i - up[cur][1] + 1 ,1,i,1);
} else {
up[cur][1] = 0;
f[1] = 0;
}
que[tail++] = 1;
ans = max( ans , f[1] );
for( j = 2; j <= m;j++) {
if( a[i][j] ) up[cur][j] = up[1-cur][j] + 1;
else up[cur][j] = 0;

while( head < tail ) {
int idx = que[tail-1];
if( up[cur][idx] >= up[cur][j] ) tail--;
else break;
}
int leftidx = 0;
if( head < tail ) leftidx = que[tail-1];

que[tail++] = j;
f[j] = f[leftidx] + get( i - up[cur][j]+1 ,leftidx+1, i , j );
//cout<<i<<" j="<<j<<" left="<<leftidx<<" f[j]="<<f[j]<<endl;
ans = max( ans , f[j] );
}
}
cout<<ans<<endl;
}
return 0;
}

/*

100
2 3 2
2 3 4
2 2 1

2 3 2
1 1 1
1 1 1

2 3 2
1 1 1
2 2 2

2 3 2
1 3 1
2 1 2

3 4 2
2 3 2 1
3 1 2 3
4 4 4 4

3 2 2
1 4
2 5
3 6

3 2 2
2 3
1 3
2 3

3 4 2
2 2 1 1
1 3 2 2
3 4 2 2

2 3 2
2 2 2
2 2 1

2 4 2
2 2 1 3
1 2 1 5

*/

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}