数组中值变换最小步长

这是Codechef长期竞赛的问题。由于竞赛已经结束，所以尴尬的我贴上了问题解决者的方法（来源：CC竞赛编辑页面）。

“数组的任何状态都可以表示为二进制掩码，每个位1表示对应的数字等于最大值，否则等于0。可以在状态R
[mask]和O（n）过渡的情况下运行DP。可以证明（或者只是相信），如果您运行良好的DP，则statest的数量将不会很大。DP的状态将是等于max的数字的掩码。当然，仅使用运算是有意义的对于这样的子数组[l;
r]，1位的数量至少等于子掩码[l;
r]中的0位的数量，因为否则其他情况都不会改变。另外，还应注意，如果您的左边界l *** 作为l时，最好仅以最大可能的r进行 *** 作（这使转换次数等于O（n））。对于C
++编码人员，使用映射结构表示所有状态也很有用。”

C / C ++代码为：

#include <cstdio>#include <iostream>using namespace std;int bc[1<<15];const int M = (1<<15) - 1;void setMin(int& ret, int c){    if(c < ret) ret = c;}void doit(int n, int mask, int currentSteps, int& currentBest){    int numMax = bc[mask>>15] + bc[mask&M];    if(numMax == n) {        setMin(currentBest, currentSteps);        return;    }    if(currentSteps + 1 >= currentBest)        return;    if(currentSteps + 2 >= currentBest)    {        if(numMax * 2 >= n) { setMin(currentBest, 1 + currentSteps);        }        return;        }    if(numMax < (1<<currentSteps)) return;    for(int i=0;i<n;i++)     {        int a = 0, b = 0;        int c = mask;        for(int j=i;j<n;j++)        { c |= (1<<j); if(mask&(1<<j)) b++; else a++; if(b >= a) {     doit(n, c, currentSteps + 1, currentBest); }        }    }}int v[32];void solveCase() {    int n;    scanf(" %d", &n);    int maxElement = 0;    for(int i=0;i<n;i++) {        scanf(" %d", v+i);        if(v[i] > maxElement) maxElement = v[i];    }    int mask = 0;    for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);    int ret = 0, p = 1;    while(p < n) {        ret++;        p *= 2;    }    doit(n, mask, 0, ret);    printf("%dn",ret);}main() {    for(int i=0;i<(1<<15);i++) {        bc[i] = bc[i>>1] + (i&1);    }    int cases;    scanf(" %d",&cases);    while(cases--) solveCase();}