OJ Board

What is answer for
are there any tricky testcases?

EDIT: bug found

You mean where S/T may be a empty string?

Well there are no such cases in the input file.

Hello!, any hint for this problem? i cant even figure out a way to get the minimum amount of strings possible by splitting T... Thanks!, Eric.

the problem can be reduced to a matching problem.

A matching problem? Matching what? Could you give more hints?

What I can think of is only a brute-force search....

Hint:
One match means you could reduce the numbers of substrings by one.

-----
Rio

Ah, so you mean using T as the nodes, and from S we get the edges? Then we need a mincost maxflow algorithm?

tobby wrote:Ah, so you mean using T as the nodes, and from S we get the edges? Then we need a mincost maxflow algorithm?

I won't say anything new, but it much helps when you think about reduction to minimum cost path cover of DAG. In CLR there is solution to minimum path cover of DAG and when someone understand it right, this task should be fairly easy.

I use the idea that I mentioned in my post and get accepted.

This task would be easy to those who have a well-coded mincost maxflow code in hand. I didn't have one, so I just apply the mcmf code in shygypsy.com.