Facebook : 构造递减数列

Given an array A of positive integers. Convert it to a decrement array with minimum cost. The only valid operation are:
Decrement with cost = 1 (only once on a number)
Delete an element completely from the array with cost = value of element

见过类似的问题，应该可以用DP解决，状态就是f[i][j]: 把前i个数弄成递减且最后一个数是j的最小代价。不过那道题每个数是有范围的，如果不限制范围不知道还能不能这么做

回复 2# darksteel


可以的，可以证明最终的数字都是原始数列里出现过的数，这样就有o(n^2)的DP了。
这个链接可以测试程序：
http://poj.org/problem?id=3666

回复 3# Narashy
全都是原数不一定吧。。比如3 4 1，最后的结果是3 3 1，代价是1。离散化倒是可以的

回复 4# darksteel

对啊，就是原来出现过的数，不一定是一一对应的。比如这里 3 3 1原来都出现过。

回复 5# Narashy
哦，那其实就是在离散化，之前没理解你的意思

恩，这题我想了很久，而且careercup上没有满意的答案，我给个答案大家看看如何，我大致的测试过：

首先因为我没找到其他规律，所以认为这题是一个NP复杂问题
其次，鉴于每个数字都是正整数，给一个伪dynamic programming的算法：

设f(i,j) == false/true. (i<n, j<sum of the array)
其中i为元数组中0~i的数列,j为costs

则有状态转移方程：
f(i,j+a[i]) = true if do not choose ith element,
f(i,j+1) = true if a[i] == a[i-1]-1,
f(i,j) = true,  if a[j] >= a[i]

回复  darksteel


可以的，可以证明最终的数字都是原始数列里出现过的数，这样就有o(n^2)的DP了。
这个链接可以测试程序：
Narashy 发表于 2011-6-12 04:15

恩，这题的确和那个ACM相似，不过这题可以delete一个数，这样造成了一些复杂。
ACM那个离散化的思想很好

回复 7# wwwyhx
有点类似，对于f[ i][j]，也就是把前i个数弄成递减，且最后一个数是j的最小代价可能由两种途径达到。对于所有可能的k >= j，有
f[ i][j] = min_k{ min{ f[i-1][k] + g(a[ i],j), f[i-1][j] + a } }
分别是把前i-1个数弄成递减且最后一个数是k的代价加上把第i个数弄成j的代价，和把前i-1个数弄成递减且最后一个数是j的代价加上把第i个数删掉的代价。这里g(a,j)就是把a弄成j需要的代价。
g(a,b)=(a>=b?(a-b):INFINITY)

回复  wwwyhx
有点类似，对于f[ i][j]，也就是把前i个数弄成递减，且最后一个数是j的最小代价可能由两种途径达到。对于所有可能的k >= j，有
f[ i][j] = min_k{ min{ f[k] + g(a[ i],j), f[j] + a } }
分别是把前i-1个数弄成递减且最后一个数是k的代价加上把第i个数弄成j的代价，和把前i-1个数弄成递减且最后一个数是j的代价加上把第i个数删掉的代价。这里g(a,j)就是把a弄成j需要的代价。
g(a,b)=(a>=b?(a-b):INFINITY)
darksteel 发表于 2011-6-15 11:03

大致看了一下，这题一个关键就是可以删除数字，写了一个O(n^4)的解法，不知道是不是可以简化，还有那个ACM题因该是O(n^3)而非O(n^2)

  //Cost(i,j) = min(Cost(i-1,j), Cost(i-2,j)+a[i-1], Cost(i-3,j)+a[i-2])
int CalcCost(int a[], int n)
{
        int nMaxCost = 0;
        int* arrSorted = new int[n];
        for (int i = 0; i < n; i++)
        {
                if (a[i] <= 0) return -1;
                nMaxCost += a[i];
                arrSorted[i] = a[i];
        }

        sort(arrSorted, arrSorted+n);

        int** pDP = new int*[n];
        for (int i = 0; i < n; i++)
                pDP[i] = new int[n];

        //initialize
        for (int i = 0; i < n; i++)
                pDP[0][i] = a[0] - arrSorted[i];

        for (int i = 1; i < n; i++)
        {
                for (int j = 0; j < n; j++)
                {
                        if (arrSorted[j] > a[i])
                                pDP[i][j] = a[i] - arrSorted[j];
                        else
                        {
                                int nMinCost = nMaxCost;
                                int nCostSum = a[i] - arrSorted[j];
                                for (int k = i-1; k >= 0; k--)
                                {
                                        for (int x = j; x < n; x++)
                                        {
                                                if (pDP[k][x] >= 0)
                                                {
                                                        if (nCostSum + pDP[k][x] < nMinCost)
                                                                nMinCost = nCostSum + pDP[k][x];
                                                }
                                        }

                                        nCostSum += a[k];
                                }

                                nMinCost = nMinCost < nCostSum ? nMinCost : nCostSum;
                                pDP[i][j] = nMinCost;
                        }
                }
        }

        //get minimum costs
        int nMinCost = nMaxCost;
        for (int i = 0; i < n; i++)
        {
                if (pDP[n-1][i] < 0) continue;
                nMinCost = nMinCost < pDP[n-1][i] ? nMinCost : pDP[n-1][i];
        }

        int nSumCost = a[n-1];
        for (int i = n-2; i >= 0; i--)
        {
                for (int j = 0; j < n; j++)
                {
                        if (pDP[i][j] >= 0)
                                nMinCost = nMinCost < pDP[i][j]+nSumCost ? nMinCost : pDP[i][j]+nSumCost;

                        nSumCost += a[i];
                }
        }

        for (int i = 0; i < n; i++)
                delete []pDP[i];
        delete []pDP;
        delete []arrSorted;

        return nMinCost;
}