tinymon's blog

NOI-'99-Sequence : Help
By tinymon, 8 years ago, In English

Hi, Can someone help me with this problem from NOI.

Thanks for any help.

PS:ko_osaga can you provide hints as u already ACd it.

Tags noi
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is a system of difference constraints on the prefix sum of the sequence.

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My idea might not be correct, but, still :

Consider l1 > l0. something like dp[n][k][0/1][0/1][0/1][0/1] which denotes, if we are processing the nth element, the range of 1's from n-l0 to n-l1, if there are k 1's in range n ... n-l0 and the [0/1] states basically determines some of the important values of the array, like n-l0, n-l0-1, n-l1, n-l1+1

→ Reply