文章目录

• 1.最大公倍数
• 2.房屋染色
• 3.字符串游戏
• 4.完美字符串

1.最大公倍数

打表找规律，发现答案肯定是max(lcm(b,b-1,b-2),lcm(b,b-1,b-3),lcm(b-1,b-2,b-3),lcm(b,b-2,b-3));

class Solution {
public:
    
     long long gcd(long long x,long long y)
    {
    return y==0?x:gcd(y,x%y);   
    }
    long long greatestcommonmultiple(int a, int b) {
        // write your code here
        long long aa=(long long)a;
        long long bb=(long long)b;
        if(aa==bb-2)
        {
            long long tmp=bb*(bb-1)/gcd(bb,bb-1);
            return tmp*(bb-2)/gcd(tmp,bb-2);
        }
        long long ma=0;
        long long tmp;
        tmp=bb*(bb-1)/gcd(bb,bb-1);
        ma=max(ma,tmp*(bb-2)/gcd(tmp,bb-2));
        tmp=bb*(bb-2)/gcd(bb,bb-2);
        ma=max(ma,tmp*(bb-3)/gcd(tmp,bb-3));
        tmp=(bb-1)*(bb-2)/gcd(bb-1,bb-2);
        ma=max(ma,tmp*(bb-3)/gcd(tmp,bb-3));
        tmp=bb*(bb-1)/gcd(bb,bb-1);
        ma=max(ma,tmp*(bb-3)/gcd(tmp,bb-3));
        return ma;
    }
};

2.房屋染色

动态规划，dp[i][j][0]表示以i为结尾染成j颜色没有步行街的最小花费，dp[i][j][1]表示以i为结尾染成j颜色有步行街的最小花费。dp[i][c1][0]=min(dp[i-1][c2][0]+costs[i][c1]),没有步行街时，必须和前一个颜色不同，且前一个也是没有步行街的状态。dp[i][c1][1]=min(dp[q][c1][0]+val[i][c1]-val[q][c1])，dp[i][c1][1]=min(dp[i-1][c2][1]+costs[i][c1])如果有步行街时，可以由之前没有步行街的状态推出，此时利用前缀和找到最小花费的转移状态。也可以由有步行街的状态推出，这与之前没有步行街时一样。

class Solution {
public:
    
     int inf=0x3f3f3f3f;
     int dp[105][105][2];
     int val[105][105];
    int paintHouseIII(vector<vector<int>> &costs, int t) {
        // Write your code here.
    memset(dp,inf,sizeof(dp));
    int n=costs.size();
    int k=costs[0].size();
    for(int j = 1; j <= k; ++j)
    dp[1][j][0] = dp[1][j][1] = costs[0][j-1];//初始化
    for(int i=1;i<=n;++i)
    for(int j=1;j<=k;++j)
    {
        if(i==1)
        val[i][j]=costs[i-1][j-1];
        else
        val[i][j]=val[i-1][j]+costs[i-1][j-1];
    }
    for(int i=2;i<=n;++i)
    for(int j=1;j<=k;++j)
    {
        for(int p=1;p<=k;++p)
        {
            if(p!=j)//不能与之前构成步行街
            {
                dp[i][j][0]=min(dp[i][j][0],dp[i-1][p][0]+costs[i-1][j-1]);
                dp[i][j][1]=min(dp[i][j][1],dp[i-1][p][1]+costs[i-1][j-1]);
            }
        }
        //能与之前构成步行街
        for(int q=i-1;q>=1;q--)
        {
            if(i-q+1>t)
            break;
            dp[i][j][1]=min(dp[i][j][1],dp[q][j][0]+val[i][j]-val[q][j]);
        }
    }
    int ans=inf;
    for(int j=1;j<=k;++j)
    ans=min(ans,min(dp[n][j][0],dp[n][j][1]));
    return ans;
    }
};

3.字符串游戏

反尼姆博弈，我们发现可以把问题转化为反尼姆博弈，26个字母分为26个石堆，每次可以从任意一堆拿出任意个石子(至少一个)，拿走最后一个石子的失败。按反尼姆博弈求解即可。

class Solution {
public:
    
     int a[26];
    bool stringGame(string &s) {
        // Write your code here.
        memset(a,0,sizeof(a));
        int ans=0;
        int num=0;
        for(int i=0;i<s.size();++i)
        {
            a[s[i]-'a']++;
        }
        for(int i=0;i<26;i++)
         {
             if(a[i])
             ans^=a[i];
             if(a[i]>1)
             num=1;
         }
         if(num)
         {
             if(ans==0)
             return false;
             else 
             return true;
         }
         else
         {
             if(ans==0)
             return true;
             else
             return false;
         }
    }
};

4.完美字符串

我们发现，无论什么情况只要把连续的0变为1就是最优的。

class Solution {
public:
    
    int perfectString(string &s, int k) {
        // Write your code here.
        int len=0;
        int ans2=0;
        for(int i=0;i<s.size();++i)
        {
            if(s[i]=='1')
            {
                ans2+=len/k+(len%k!=0);
                len=0;
            }
            else
            len++;
        }
        ans2+=len/k+(len%k!=0);
        return ans2;
    }
};