K. 宝石序列

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 484K, 提交时间: 2019-06-02 15:55:40

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickpow(ll x,ll y,ll z)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%z;
        x=x*x%z;
        y>>=1;
    }
    return ans;
}
ll phi(ll n)
{
    ll i,rea=n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            rea=rea-rea/i;
            while(n%i==0)
                n/=i;
         }
    }
    if(n>1)
        rea=rea-rea/n;
    return rea;
}

const int N=55;
const int inf=1e9+7;
char s[N]; 
int dp[N][N],f[N][N];
int main(){
    scanf("%s",s+1); int n=strlen(s+1);
    for(int i=0;i<N;i++)for(int j=i;j<N;j++)dp[i][j]=inf;
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int i=n;i>=1;i--){
        for(int j=0;j<N;j++)for(int k=0;k<N;k++)f[j][k]=inf;
        f[i][1]=0;
        for(int j=i+1;j<=n;j++){
            if(s[j]!=s[i])continue;
            for(int x=i;x<j;x++){
                if(s[x]!=s[i])continue;
                for(int k=1;k<=n;k++){
                    f[j][k]=min(f[j][k],f[x][k-1]+dp[x+1][j-1]);
                }
            }
        }
        for(int j=i+1;j<=n;j++){
            for(int k=i;k<=j;k++){       
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                dp[i][j]=min(dp[i][j],f[j][3]+1);
                dp[i][j]=min(dp[i][j],f[j][9]+1);
                dp[i][j]=min(dp[i][j],f[j][27]+1);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}



/*
int main()
{
    while(scanf("%s",a)!=EOF)
    {
        x = 4;
        z = 1e9+7;
        ll len=strlen(a);
        if (len == 1 && a[0] == '0') break;
        ll p=phi(z);
        ll ans=0;
        for(ll i=0;i<len;i++)
            ans=(ans*10+a[i]-'0')%p;
        ans+=(p-1);
        ll w1 = quickpow(x,ans,z);
        x = 2;
        ll w2 = quickpow(x,ans,z);
        ll ww = (w1 + w2) % z;
        printf("%lld\n", ww);
    }
    return 0;
}
*/

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 508K, 提交时间: 2021-04-27 10:50:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=55;
const int inf=1e9+7;
char s[N];
int dp[N][N],f[N][N];
int main(){
    scanf("%s",s+1); int n=strlen(s+1);
    for(int i=0;i<N;i++)for(int j=i;j<N;j++)dp[i][j]=inf;
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int i=n;i>=1;i--)
	{
        for(int j=0;j<N;j++)for(int k=0;k<N;k++)f[j][k]=inf;
        f[i][1]=0;
        for(int j=i+1;j<=n;j++)
		{
            if(s[j]!=s[i])continue;
            for(int x=i;x<j;x++)
			{
                if(s[x]!=s[i])continue;
                for(int k=1;k<=n;k++){
                    f[j][k]=min(f[j][k],f[x][k-1]+dp[x+1][j-1]);
                }
            }
    	}
		for(int j=i+1;j<=n;j++)
		{
            dp[i][j]=min(dp[i][j],f[j][3]+1);
                dp[i][j]=min(dp[i][j],f[j][9]+1);
                dp[i][j]=min(dp[i][j],f[j][27]+1);
			for(int k=i;k<=j;k++){     
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                
            }
        }
    }
    printf("%d",dp[1][n]); 
    return 0;
}

详情