Noip2000 总结

tcswuzb · 2018-10-18 14:39:57 · 个人记录

T1

本题与那道题十分类似

我们可以设置一个四维DP

注意一定要判断i==k\ 并且j==h\ 的情况

这种情况下只可以算一次

CODE:

#include<bits/stdc++.h> 
using namespace std;
int max(int a,int b){
    return a>b? a:b;
}
int a[51][51];
int sum[51][51][51][51];
int n,i,j,h,k,x,y,z;
int main()
{
    scanf("%d%d%d%d",&n,&x,&y,&z);
    while(x&&y&&z)
    {
        a[x][y]=z;
        scanf("%d%d%d",&x,&y,&z);
    }
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      for(h=1;h<=n;h++)
       for(k=1;k<=n;k++)
       {
          int tmp1=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]);
          int tmp2=max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]);
          sum[i][j][h][k]=max(tmp1,tmp2)+a[i][j];
          if(i!=h&&j!=k) sum[i][j][h][k]+=a[h][k];
       }
    printf("%d\n",sum[n][n][n][n]);   
    return 0;
}

T2

这是一道十分经典的区间DP题

CODE:

ll n,k;
ll num[45],dp[45][10];
IL ll yunsk(ll le,ll ri)
{
    ll tot=0;
    for(R ll i=le;i<=ri;++i)
    tot=(tot<<1)+(tot<<3)+num[i];
    return tot;
}
int main()
{
    read(n);read(k);
    for(R ll i=1;i<=n;++i) scanf("%1lld",&num[i]);
    for(R ll i=1;i<=n;++i) dp[i][0]=yunsk(1,i);
    for(R ll i=1;i<=n;++i)
     for(R ll j=1;j<=min(k,i-1);++j)
      for(R ll k=j;k<i;++k)
       dp[i][j]=max(dp[i][j],dp[k][j-1]*yunsk(k+1,i));
    printf("%lld\n",dp[n][k]);   
    return 0;
}

上述代码只有60分 因为最后的计算结果可能会十分大

所以我们需要使用高精度计算

CODE:

int n,k;
int num[1001];
struct Node{
    int a[101];
}dp[110][110];
Node mul(Node X,int le,int ri)
{
    Node Y,Z;
    memset(Y.a,0,sizeof Y.a);
    memset(Z.a,0,sizeof Z.a);
    Y.a[0]=ri-le+1;
    for(R int i=ri;i>=le;--i)
    Y.a[ri-i+1]=num[i];
    for(R int i=1;i<=X.a[0];++i)
     for(R int j=1;j<=Y.a[0];++j)
     {
       Z.a[i+j-1]+=X.a[i]*Y.a[j];
       Z.a[i+j-1+1]+=Z.a[i+j-1]/10;
       Z.a[i+j-1]%=10;
     }
    Z.a[0]=X.a[0]+Y.a[0]-1;
    for(R int i=1;i<=Z.a[0];++i)
    {
        Z.a[i+1]+=Z.a[i]/10;Z.a[i]%=10;

    }
    if(Z.a[Z.a[0]+1]) Z.a[0]++;
    return Z;
}
Node Max(Node A,Node B)
{
    if(A.a[0]>B.a[0]) return A;
    else if(A.a[0]<B.a[0]) return B;
    else
    {
        for(R int i=A.a[0];i;--i)
        if(A.a[i]>B.a[i]) return A;
        else if(A.a[i]<B.a[i]) return B;
        return A;
    }
}
IL void print(Node A)
{
    for(R int i=A.a[0];i;--i)
    printf("%d",A.a[i]);

}
int main()
{
    read(n);read(k);
    for(R int i=1;i<=n;++i) scanf("%1d",&num[i]);
    for(R int i=1;i<=n;++i)
    for(R int j=i;j;--j)
    dp[i][0].a[++dp[i][0].a[0]]=num[j];
    for(R int i=2;i<=n;++i)
     for(R int j=1;j<=min(i-1,k);++j)
      for(R int k=j;k<i;++k)
       dp[i][j]=Max(dp[i][j],mul(dp[k][j-1],k+1,i)); 
    print(dp[n][k]);    
    return 0;
}

T3

题意分析

首先我们可以发现

-15/-2=-7 -15%-2=-1

但是我们想要的是-15%-2=1

所以我们应该在负数且无法整除时判断一下

然后就是递归求解的事了

CODE:

char key[20]={'0','1','2','3','4','5','6','7','8','9','A',
'B','C','D','E','F','G','H','I','J'};
int n,m;
IL void ans_cf(int x,int y)
{
    if(!x) return;
    else if(x>0 || x%y==0)
    {
        ans_cf(x/y,y);
        printf("%c",key[x%y]);
        return;
    }
    else
    {
        ans_cf(x/y+1,y);
        printf("%c",key[x%y-y]);
        return;
    }
}
int main()
{
    read(n);read(m);
    printf("%d=",n);
    ans_cf(n,m);
    printf("(base%d)\n",m);
    return 0;
}

T4

这道题一看就知道是搜索

每一次直接枚举制胡窜 查看是否可以拼接上

同时 一个制胡窜如果使用>=2次的话就不能够在使用了

CODE:

int n,ans;
string key[51];
int vis[50];
IL int link(string s1,string s2)
{
    for(R int i=1;i<min(s1.length(),s2.length());++i)
    {
        int ok=1;
        for(R int j=0;j<i;++j)
        {
            if(s2[j]!=s1[s1.length()-i+j]) {ok=0;break;}
        }
        if(ok) return i;
    }
    return 0;
}
IL void dfs(string now,int len)
{
    ans=max(len,ans);
    for(R int i=0;i<n;++i)
    {
        if(vis[i]>=2) continue;
        int res=link(now,key[i]);
        if(res)
        {
            vis[i]++;
            dfs(key[i],len+key[i].length()-res);
            vis[i]--;
        }
    }
}
int main()
{
    read(n);
    for(R int i=0;i<=n;++i) vis[i]=0,cin>>key[i];
    dfs(' '+key[n],1);
    printf("%d",ans);
    return 0;
}