t****t 发帖数: 6806 | 1 gcj 2-D咋做, 我实在是totally no idea |
T*******i 发帖数: 4992 | 2 地址?
【在 t****t 的大作中提到】 : gcj 2-D咋做, 我实在是totally no idea
|
p**s 发帖数: 2707 | 3 把字符串分成长度为k的子串,每个子串的第一个字符组成A1,第二个组成A2... Ak
对于Ai,Aj,定义M_ij为AiAj对应字符相等的个数,N_ij为Ai和Aj下一个字符相同的个数
需要找到N_i1j1和M_i2j2,M_i3j3...M_ikjk,使他们的和最大
如果对每个N_ij,在M除去第i行j列的的(k-1)*(k-1)矩阵里找和最大的不同行不同列的
k-1个元素,使和最大,用匈牙利算法,一共需要O(k^5)
应该有更快的方法
【在 t****t 的大作中提到】 : gcj 2-D咋做, 我实在是totally no idea
|
p**s 发帖数: 2707 | 4 哦,不对,实际上变成了找最短哈密尔顿圈的问题。。。成了NP-complete...
【在 p**s 的大作中提到】 : 把字符串分成长度为k的子串,每个子串的第一个字符组成A1,第二个组成A2... Ak : 对于Ai,Aj,定义M_ij为AiAj对应字符相等的个数,N_ij为Ai和Aj下一个字符相同的个数 : 需要找到N_i1j1和M_i2j2,M_i3j3...M_ikjk,使他们的和最大 : 如果对每个N_ij,在M除去第i行j列的的(k-1)*(k-1)矩阵里找和最大的不同行不同列的 : k-1个元素,使和最大,用匈牙利算法,一共需要O(k^5) : 应该有更快的方法
|
w****i 发帖数: 964 | 5 枚举一下所有的permutation, 好象不难啊,难道我理解错了? |
w****i 发帖数: 964 | 6 又看了一下,原来有个k=16的
never mind ... |
T*****9 发帖数: 2484 | 7 我还没看。。。我一看来不及了就打quake了
你可以下载别人的solution啊
【在 t****t 的大作中提到】 : gcj 2-D咋做, 我实在是totally no idea
|
t****t 发帖数: 6806 | 8 我没参加, 不能下载
【在 T*****9 的大作中提到】 : 我还没看。。。我一看来不及了就打quake了 : 你可以下载别人的solution啊
|
T*****9 发帖数: 2484 | 9 ACRush的
【在 t****t 的大作中提到】 : gcj 2-D咋做, 我实在是totally no idea
|
t****t 发帖数: 6806 | 10 谢谢, 我先想想再看答案. 本来就想要个提示的
【在 T*****9 的大作中提到】 : ACRush的
|
T*****9 发帖数: 2484 | 11 不好意思啊
我这题没看。。。最近忙,打算忙完了再看google code jam
【在 t****t 的大作中提到】 : 谢谢, 我先想想再看答案. 本来就想要个提示的
|
t****t 发帖数: 6806 | 12 我想明白了, 就是得这么做
你刚才说hamilton loop把我绕了一下, 其实就是个traveling salesman问题, n^2*2^n
对于16应该还是可以接受的
【在 p**s 的大作中提到】 : 哦,不对,实际上变成了找最短哈密尔顿圈的问题。。。成了NP-complete...
|
p**s 发帖数: 2707 | 13 我是文科生,能想到这一步已经不容易了
【在 t****t 的大作中提到】 : 我想明白了, 就是得这么做 : 你刚才说hamilton loop把我绕了一下, 其实就是个traveling salesman问题, n^2*2^n : 对于16应该还是可以接受的
|
t****t 发帖数: 6806 | 14 嗯, 很牛的文科生(其实你骗谁啊, 你不是文科生)
【在 p**s 的大作中提到】 : 我是文科生,能想到这一步已经不容易了
|