Problem: grading (2019 round2)

Due to a convenient recent teaching vacancy, Laz Y. has suddenly landed a job
as a schoolteacher. Known to his students as Mr. Y, he's prepared to provide a
comprehensive, fairly-evaluated educational experience — as long as it doesn't
take too much effort.

Mr. Y's first order of business in his new role will be grading recent exams
from two different subjects: art and biology. He has been handed **S** stacks
of **H** exam papers each. The _i_th paper from the top in the _j_th stack is
either from the art exam (if **Pi,j** = "A"), or otherwise from the biology
exam (if **Pi,j** = "B").

Mr. Y will go about the grading process as follows: At each point in time,
he'll select a stack which still contains at least one exam paper, and remove
its topmost paper. He'll then either grade that paper, or accidentally "lose"
it and assign its owner a random grade instead. Either way, once he's done
with that paper, he'll repeat the process of selecting a new paper until all
of the stacks are empty and all **H*****S** papers have been dealt with.

There are few things that Mr. Y hates as much as context switching. For
example, it's very troublesome to jump from grading an art exam to a biology
one! (Or from relaxing to doing any work at all.) Each time Mr. Y begins a
grading a paper, he must make a context switch if this is either the first
paper he's choosing to grade, or if its subject is different than that of the
previous paper that he graded. Note that this entirely excludes any "lost"
papers.

Mr. Y is no fool — he realizes that his evaluations would be too suspiciously
inaccurate if he were to simply lose all **H*****S** papers. Even losing a
smaller number of them may prove too suspicious. Therefore, he'll imagine
**K** different theoretical scenarios, such that in the _i_th one, he will
allow himself to lose at most **Li** papers throughout the grading process
(with **L1..K** all being distinct). Independently for each scenario, he'd
like to determine the minimum number of context switches he would need to make
throughout the process.

### Input

Input begins with an integer **T**, the number of days Mr. Y spends grading
exams. For each day, there is first a line containing the space-separated
integers **H**, **S**, and **K**. Then, **H** lines follow, the _i_th of which
contains the length-**S** string **Pi,1..S**. Then, a final line follows
containing the **K** space-separated integers **L1** through **LK**.

### Output

For the _i_th day, print a line containing "Case #_i_: " followed by **K**
space-separated integers, the _j_th of which is the minimum number of context
switches which Mr. Y would need to make if he were to grade the papers while
losing at most **Lj** of them.

### Constraints

1 ≤ **T** ≤ 200  
1 ≤ **H**, **S** ≤ 300  
1 ≤ **K** ≤ **H** * **S**  
0 ≤ **Li** ≤ **H** * **S** \- 1  

### Explanation of Sample

In the first case, if Mr. Y may only lose one paper, the best he can do is
make two context switches, for example by grading the B papers from the first
and third stacks, then losing the B paper from the fifth stack, and then
grading the A papers from the second and fourth stacks. On the other hand, the
freedom to lose two papers would allow him to make only one context switch,
for example by losing the A papers from the second and fourth stacks and then
grading the B papers from the first, third, and fifth stacks.

In the second case, if Mr. Y may lose one paper, one optimal strategy
(requiring just two context switches) is as follows:

  1. Grade the B paper from the top of stack 2 (first context switch). 
  2. Lose the A paper from the top of stack 3. 
  3. Grade the B paper from the top of stack 3. 
  4. Grade the A paper from the top of stack 1 (second context switch). 
  5. Grade the A paper from the top of stack 1. 
  6. Grade the A paper from the top of stack 2. 



Sample input:
5
1 5 2
BABAB
1 2
2 3 3
ABA
AAB
1 0 5
3 2 4
AB
BA
AB
0 1 2 3
5 5 6
BBABA
ABAAB
AAABA
BABBA
BBBAB
5 0 8 12 10 1
10 10 15
AABAAABBAB
BAABAAAABB
AABABBBABB
BAAABAAAAB
BBBBAAABAA
ABAABBBABA
BABAABABBA
AAABAAABAA
BAAAABBBBA
ABABBAAABA
14 2 99 33 3 8 43 4 12 1 21 24 17 32 10


Sample output:
Case #1: 2 1
Case #2: 2 3 1
Case #3: 4 3 2 1
Case #4: 3 5 2 1 2 4
Case #5: 5 8 1 2 8 7 1 7 5 9 4 3 4 3 6



Code: // Grading
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 302
#define LIM2 90001

int H,S,K;
char P[LIM][LIM];

// dyn[i][s][p] = min discards for at most s context switches in the first i papers in stack,
// with current paper type being p
int dyn[LIM][LIM][2];

// minD[f][s] = min total discards for at most s context switches assuming first paper type is f
int minD[2][LIM];

// ans[d] = min total context switches for at most d discards
int ans[LIM2];

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,j,f,s,p,d;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(H),Read(S),Read(K);
				Fox(i,H)
					scanf("%s",&P[i]);
			// DP on each stack
			Fill(minD,0);
				Fox(f,2)
					Fox(j,S)
					{
						Fill(dyn,60);
							Fox(s,H+1)
								dyn[0][s][f]=0;
							Fox(i,H)
								Fox(s,H+1)
									Fox(p,2)
									{
										d=dyn[i][s][p];
										int p2=P[i][j]-'A';
										Min(dyn[i+1][s+(p2==p ? 0 : 1)][p2],d); // grade
										Min(dyn[i+1][s][p],d+1); // discard
									}
							Fox(s,H+1)
								minD[f][s]+=min(dyn[H][s][0],dyn[H][s][1]);
					}
			// compute answers
			Fill(ans,60);
				Fox(f,2)
					Fox(s,H+1)
						Min(ans[minD[f][s]],s);
				Fox(d,H*S)
					Min(ans[d+1],ans[d]);
			// process queries
			printf("Case #%d:",t);
				while (K--)
				{
					Read(d);
					printf(" %d",ans[d]+1);
				}
			printf("\n");
		}
	return(0);
}