Topcoder SRM548 div2

250pt：水題。

500pt：二份答案，判定枚舉出的答案是否能夠将數組變成單調增的。

代碼：

class KingdomAndTrees
{
        public:

        bool Check(int t,vector<int> heights)
        {
            int i,j,n;
            n=heights.size();
            for (i=0;i<n;i++)
            {
                if (i==0) heights[0]=max(heights[0]-t,1);
                else
                {
                    if (heights[i]+t<=heights[i-1]) return false;
                    if (heights[i]-t<=heights[i-1])
                    {
                        heights[i]=heights[i-1]+1;
                    }
                    else
                    {
                        heights[i]-=t;
                    }
                }
            }
            return true;
        }

        int minLevel(vector<int> heights)
        {
            int l,r,mid,i,j,n;
            n=heights.size();
            l=0;
            r=INF;
            while(l<=r)
            {
                mid=(l+r)/2;
                if (Check(mid,heights)==true) r=mid-1;
                else l=mid+1;
            }
            return l;
        }


};
           

1000pt：比賽的時候結束前3min交的，寫的倉促，有一些細節寫錯了，導緻比賽的時候挂了。

dp[i]，i表示狀态，即使用了原密碼的哪幾位資料，然後維護一個前幾位比原密碼大的，前幾位與原密碼相等，比原密碼小的三個數，那麼。

假設狀态p能轉移到i，那麼有

如果p的前幾位存在與原密碼相等，那麼，如果新加進來那個數符合條件，且新加進來這個數與原密碼相應的位置上的數相等，那麼i的與原密碼相等的值更新，如果比原密碼相應位置上的數大，更新i的比原密碼大的值，否則更新i的比原密碼小的值。

否則，通過p的比原密碼大的值和比原密碼小的值更新i的大值和小值。

代碼

typedef struct
{
    long long big;
    long long equal;
    long long small;
}DP;

class KingdomAndPassword
{
        public:

        DP dp[(1<<16)+5];
        int count[(1<<16)+5];
        long long ten[17];

        long long newPassword(long long oldPassword, vector<int> restrictedDigits)
        {
            int i,j,n,t,tag,p;
            int old[20];
            long long pp;
            pp=oldPassword;
            n=0;
            while(oldPassword)
            {
                old[n++]=oldPassword%10;
                oldPassword/=10;
            }
            oldPassword=pp;
            for (i=0;i<n/2;i++)
            {
                t=old[i];
                old[i]=old[n-i-1];
                old[n-i-1]=t;
            }
            ten[0]=1;
            for (i=1;i<=n;i++)
            {
                ten[i]=ten[i-1]*10;
            }
            memset(count,0,sizeof(count));
            for (i=0;i<(1<<n);i++)
            {
                for (j=0;j<n;j++)
                {
                    if ((i & (1<<j))!=0) count[i]++;
                }
            }
            dp[0].big=0;
            dp[0].small=0;
            dp[0].equal=0;
            for (i=1;i<(1<<n);i++)
            {
                dp[i].small=0;
                dp[i].big=INF;
                for (j=0;j<n;j++)
                {
                    if ((i & (1<<j))==0) continue;
                    tag=old[j];
                    if (restrictedDigits[count[i]-1]==tag) continue;
                    p=i & (~(1<<j));
                    if (tag==old[count[i]-1] && count[i]==1)
                    {
                        dp[i].equal=tag*ten[n-count[i]];
                        continue;
                    }
                    if (count[i]==1)
                    {
                        if (tag>old[count[i]-1]) dp[i].big=min(dp[i].big,tag*ten[n-count[i]]);
                        if (tag<old[count[i]-1]) dp[i].small=max(dp[i].small,tag*ten[n-count[i]]);
                        continue;
                    }
                    if (dp[p].equal!=0)
                    {
                        if (tag>old[count[i]-1]) dp[i].big=min(dp[i].big,dp[p].equal+tag*ten[n-count[i]]);
                        if (tag==old[count[i]-1]) dp[i].equal=dp[p].equal+tag*ten[n-count[i]];
                        if (tag<old[count[i]-1]) dp[i].small=max(dp[i].small,dp[p].equal+tag*ten[n-count[i]]);
                    }
                    else
                    {
                        if (dp[p].big!=INF) dp[i].big=min(dp[i].big,dp[p].big+tag*ten[n-count[i]]);
                        if (dp[p].small!=0) dp[i].small=max(dp[i].small,dp[p].small+tag*ten[n-count[i]]);
                    }
                }
            }
            if (dp[(1<<n)-1].equal!=0) return dp[(1<<n)-1].equal;
            if (dp[(1<<n)-1].small==0 && dp[(1<<n)-1].big==INF) return -1;
            if (dp[(1<<n)-1].small!=0 && dp[(1<<n)-1].big!=INF)
            {
                return oldPassword-dp[(1<<n)-1].small<=dp[(1<<n)-1].big-oldPassword?dp[(1<<n)-1].small:dp[(1<<n)-1].big;
            }
            if (dp[(1<<n)-1].small!=0) return dp[(1<<n)-1].small;
            return dp[(1<<n)-1].big;
        }
};