小编n00*_*d3r的帖子

我最近遇到过这个问题.假设x轴上有n个点,x [0],x [1] .. x [n-1].让与这些点中的每一个相关联的权重为w [0],w [1] ... w [n-1].从0到n-1之间的任何点开始,目标是覆盖所有点,使得w [i]*d [i]的总和最小化,其中d [i]是到达第i个点所覆盖的距离.起点.

示例:
假设点数为:1 5 10 20 40
假设权重为:1 2 10 50 13
如果我选择从点10开始并选择移动到点20然后到5然后再到40然后最终到1,那么加权和将变为10*0 + 50*(10)+ 2*(10 + 15)+ 13*(10 + 15 + 35)+ 1*(10 + 15 + 35 + 39).

我试图通过贪婪的方法解决它,从具有最大相关权重的点开始并移动到第二个最大权重点,依此类推.但算法不起作用.有人可以指点一下解决这个问题必须采取的方法吗？

我在考虑以下问题:给定一个字符串S,让第i ^个子字符串的长度为l _i,第i ^个子字符串的出现次数为o _i.打印子字符串,使l _i*o _i最大化.

我有这个问题的O(n ³)解决方案(蛮力),我生成所有子串并找到具有最大值的子串.我的代码如下:

public static void solve(String S) {
    long max = Integer.MIN_VALUE;
    String res = "";
    for (int i = 0; i < S.length(); i++) {
        for (int j = 1; j <= S.length() - i; j++) {
            String s = S.substring(i, i + j);
            int o = countOccurrences(S, s);
            long p = (long) o * (long) s.length();
            if (max < p) {
                max = p; …