OJ Board

You can solve this problem by using DP.

1) Keep Length and The number of ways.

2) Are these different? (AABC, CBA ..... )

matrix[i][s][l] = max[v = s ~ s + l - 1](matrix[i - 1][s][v - s] + v, matrix[i][v + 1][(s + l) - v - 1] + v)

you can get matrix[i][s][l] mean in before post.

I don`t understand why i got WA

this is my code


#include <iostream>

#define MAXL 1000002

using namespace std;

char M[MAXL];
int L[MAXL];

int main(){
int casen = 1;
int n;
int last_fill, len;
int x, y;
char value;

while(cin >> M){
len = strlen(M);

cin >> n;
value = M[0];
last_fill ...

I got accept by using DP.

I use 3-dimension matrix.

matrix[k][s][l]

k is capcity the number of mailbox.

s is start the number of crackers

l is length...

so matrix[k][s][l] mean is i have 1 mailbox and..

minimum the number of crackers in range s, s + 1, s+ 2 , .... , (s + l - 1)

sorry I can ...

I used STL map O(n^2) (or n^2lgn)

But I got TLE T_T

Is map too slow to solve this problem?

This is my code..


#include<iostream>
#include<map>

using namespace std;

int main(){
int num, cnt;
long long input;
long long max, z;
map<long long, int> M;
while (cin >> num){
cnt = 0;
max = 0 ...

.. Because of Initialize..

That is 2-th Array;;;;;

Couldn`t Initialize memset

This is Floyd Version Code . This code return WA

cut after AC..,


This is BFS Version.. This code return TLE

#include <iostream>
#include <vector>
#include <queue>

#define min(x, y) (x<y)?x:y
#define MAXN 101

using namespace std;

struct node {
int first;
int second;
bool path[MAXN ...