题解

38 条题解

  • 3
    @ 2018-05-02 21:18:11

    三维dp

    #include<cstdio>
    #define max(a,b) a>b?a:b
    #define r(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    int f[41][41][41],a[351],n,m,g[4],t;
    int main()
    {
        scanf("%d%d",&n,&m);
        r(i,1,n) scanf("%d",&a[i]);
        while(m--) {scanf("%d",&t);g[t-1]++;}
        f[0][0][0]=0;
        r(i,0,g[0])
        r(j,0,g[1])
        r(k,0,g[2])
        r(l,0,g[3])
        {
            t=a[1+i+(j<<1)+k*3+(l<<2)];
            if(j) f[j][k][l]=max(f[j][k][l],f[j-1][k][l]);
            if(k) f[j][k][l]=max(f[j][k][l],f[j][k-1][l]);
            if(l) f[j][k][l]=max(f[j][k][l],f[j][k][l-1]);
            f[j][k][l]+=t;
        }
        printf("%d",f[g[1]][g[2]][g[3]]);
    }
    
  • 2
    @ 2018-01-30 17:17:00

    DP基础题:
    由于题目告诉我们确保用完牌恰好能走完,题目被大大简化
    我们用数组dp[a][b][c][d]表示用了a张一步牌,b张2步牌,c张3步牌,d张4布牌所能得到的最高分
    num[i-1]表示i步牌的张数;path[]数组记录路径信息;card[]数组记录卡牌信息。
    则有dp[0][0][0][0]=path[0]//什么牌都不用就可以获得起点的分数
    并且有**path[a+2b+3c+4d]为当前点的分数**
    之后四重循环,分别枚举a,b,c,d;
    对于枚举的每种情况:
    dp[a][b][c][d]=max(dp[a][b][c][d],**之前的一步操作**+**[a+2b+3c+4d]**)
    这句话的意思是:**是不进行前一步操作比较赚还是进行比较赚**
    为什么要判断a,b,c,d是否大于0呢?**都没牌了哪里还存在前一步操作呢?**
    ok!最后答案被保存在dp[num[0]][[num[1]][num[2]][num[3]]里,输出即可。
    talk is cheap shou me the code:
    #include<iostream>
    using namespace std;
    int N,M,pv,num[4],path[500],card[500],dp[42][42][42][42];
    int main()
    {
    cin>>N>>M;
    for(int i=0;i<N;i++)cin>>path[i];
    for(int i=0;i<M;i++){cin>>card[i];num[card[i]-1]+=1;}
    dp[0][0][0][0]=path[0];
    for(int a=0;a<=num[0];a++)
    for(int b=0;b<=num[1];b++)
    for(int c=0;c<=num[2];c++)
    for(int d=0;d<=num[3];d++)
    {pv=a+b*2+c*3+d*4;
    if(a>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]+path[pv]);
    if(b>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]+path[pv]);
    if(c>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]+path[pv]);
    if(d>0) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]+path[pv]);}
    cout<<dp[num[0]][num[1]][num[2]][num[3]];
    return 0;
    }

    • @ 2018-01-30 17:23:15

      写的不错

  • 0
    @ 2017-10-30 23:20:17

    simple dp
    f[i][j][k][l]表示用了i张前进1的卡片,j张前进2的卡片,k张前进3的卡片和l张前进d的卡片。dp的时候直接枚举每一个。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    int n,m;
    int a[400],b[400],cnt[5];
    int f[45][45][45][45];
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i],cnt[b[i]]++;
        for(int a1=0;a1<=cnt[1];a1++)
            for(int a2=0;a2<=cnt[2];a2++)
                for(int a3=0;a3<=cnt[3];a3++)
                    for(int a4=0;a4<=cnt[4];a4++)
                    {
                        if(a1)
                            f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1-1][a2][a3][a4]);
                        if(a2)
                            f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2-1][a3][a4]);
                        if(a3)
                            f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2][a3-1][a4]);
                        if(a4)
                            f[a1][a2][a3][a4]=max(f[a1][a2][a3][a4],f[a1][a2][a3][a4-1]);
                        f[a1][a2][a3][a4]+=a[a1+2*a2+3*a3+4*a4+1];
                    }
        printf("%d\n",f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
        return 0;
    }
    
    
  • 0
    @ 2017-10-28 08:13:02

    简单的DP

    #include<bits/stdc++.h>
    using namespace std;
    int a[400];
    int f[41][41][41][41];
    int main()
    {
        int n,m,x,s1=0,s2=0,s3=0,s4=0,s;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            if(x==1)
            {
                s1++;
            }
            else if(x==2)
            {
                s2++;
            }
            else if(x==3)
            {
                s3++;
            }
            else
            {
                s4++;
            }
        }
        f[0][0][0][0]=a[1];
        for(int i=0;i<=s1;i++)
        {
            for(int j=0;j<=s2;j++)
            {
                for(int k=0;k<=s3;k++)
                {
                    for(int h=0;h<=s4;h++)
                    {
                        s=0;
                        if(i!=0)
                        {
                            s=max(s,f[i-1][j][k][h]);
                        }
                        if(j!=0)
                        {
                            s=max(s,f[i][j-1][k][h]);
                        }
                        if(k!=0)
                        {
                            s=max(s,f[i][j][k-1][h]);
                        }
                        if(h!=0)
                        {
                            s=max(s,f[i][j][k][h-1]);
                        }
                        f[i][j][k][h]=s+a[i+2*j+3*k+4*h+1];
                    }
                }
            }
        }
        printf("%d",f[s1][s2][s3][s4]);
        return 0;
    }
    
  • 0
    @ 2017-07-18 20:58:16

    DP

    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    const int MAXN = 355;
    const int MAXM = 125;
    int n, m, a[MAXN], b[MAXM], am[5];
    int dp[41][41][41][41];
    
    int main(){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++) scanf("%d", &b[i]), am[b[i]]++;
        dp[0][0][0][0] = a[1];
        for(int i = 0; i <= am[1]; i++){
            for(int j = 0; j <= am[2]; j++){
                for(int k = 0; k <= am[3]; k++){
                    for(int l = 0; l <= am[4]; l++){
                        int t = i+2*j+3*k+4*l+1;
                        if(i>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l]+a[t]);
                        if(j>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]+a[t]);
                        if(k>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]+a[t]);
                        if(l>=1)    dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]+a[t]);
                    }
                }
            }
        }
        printf("%d", dp[am[1]][am[2]][am[3]][am[4]]);
        return 0;
    }
    
  • 0
    @ 2016-08-17 15:47:03
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    #define rep(i,a,b) for (int i=a;i<=b;++i)
    int f[41][41][41][41], a[350], t, num[5];
    int n,m;
    inline int max(int x,int y) {return x>y?x:y;}
    int main(){
            scanf("%d%d",&n,&m);
            memset(f,0,sizeof f);
            memset(num,0,sizeof num);
            rep(i,1,n) scanf("%d",&a[i]);
            rep(i,1,m) scanf("%d",&t), ++num[t];
            rep(i,0,num[1]) rep(j,0,num[2]) rep(k,0,num[3]) rep(l,0,num[4]){
                    int temp = 0;
                    if (i) temp = max(temp, f[i-1][j][k][l]);
                    if (j) temp = max(temp, f[i][j-1][k][l]);
                    if (k) temp = max(temp, f[i][j][k-1][l]);
                    if (l) temp = max(temp, f[i][j][k][l-1]);
                    f[i][j][k][l] = temp + a[i*1+j*2+k*3+l*4+1];
            }
            cout << f[num[1]][num[2]][num[3]][num[4]] << endl;
            return 0;
    }
    
    

    有2000年代风格的题目
    f[i][j][k][l]表示各型号的卡用了几次
    随便dp

    注意有个坑:
    棋子是从1开始跳的,而不是从0开始

  • 0
    @ 2016-08-15 09:16:32
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int maxn = 350 + 5;
    const int maxm = 120 + 5;
    const int maxtype = 40 + 5;
    
    int n, m;
    int score[maxn];
    int card[5];
    int d[maxtype][maxtype][maxtype][maxtype];
    
    int dp (int coordi, int c1, int c2, int c3, int c4) {
        int& ans = d[c1][c2][c3][c4];
        if (ans >= 0) return ans;
        
        ans = 0;
        int v = score[coordi];
        if (c1) ans = max(ans, dp(coordi+1, c1-1, c2, c3, c4)+v);
        if (c2) ans = max(ans, dp(coordi+2, c1, c2-1, c3, c4)+v);
        if (c3) ans = max(ans, dp(coordi+3, c1, c2, c3-1, c4)+v);
        if (c4) ans = max(ans, dp(coordi+4, c1, c2, c3, c4-1)+v);
        
        return ans;
    }
    
    int main ()
    {
    //  freopen("in.txt", "r", stdin);
        memset(d, -1, sizeof(d));
        
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> score[i];
        for (int i = 0; i < m; i++) {
            int tmp; cin >> tmp;
            card[tmp]++;
        }
        
        d[0][0][0][0] = score[n-1];
        cout << dp(0, card[1], card[2], card[3], card[4]);
        return 0;
    }
    
  • 0
    @ 2016-07-22 18:01:13

    位置是可以用爬行卡算来的!!!
    这一道水题居然花了一个小时、、不可思议
    ``` c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;

    int N[400], M[200], n, m;
    int num[5];
    int dp[41][41][41][41];

    inline int pos(int a, int b, int c, int d) {
    return 1+a+(b)*2+(c)*3+(d)*4;
    }

    int main()
    {
    memset(dp, 0, sizeof dp);
    memset(num, 0,sizeof num);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    scanf("%d", &N[i]);
    for (int i = 1; i <= m; i++) {
    scanf("%d", &M[i]);
    num[M[i]]++;
    }
    for (int i = 0; i <= num[1]; i++)
    for (int j = 0; j <= num[2]; j++)
    for (int k = 0; k <= num[3]; k++)
    for (int l = 0; l <= num[4]; l++) {
    int p = pos(i,j,k,l);
    if (i != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l]+N[p]);
    if (j != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]+N[p]);
    if (k != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]+N[p]);
    if (l != 0) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]+N[p]);
    }
    cout << dp[num[1]][num[2]][num[3]][num[4]]+N[1] << endl;
    return 0;
    }

  • 0
    @ 2016-01-27 07:00:21

    #include<iostream>
    #include<cstring>
    using namespace std;
    int f[41][41][41][41],a[401],b[5],n,m;
    int max(int x,int y)
    {
    if (x>y) return x;
    else return y;
    }
    int main()
    {
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    for (int i=1;i<=m;i++)
    {
    int k;
    cin>>k;
    b[k]++;
    }

    memset(f,0,sizeof(f));
    f[0][0][0][0]=a[1];
    for (int i=0;i<=b[1];i++)
    {
    for (int j=0;j<=b[2];j++)
    {
    for (int k=0;k<=b[3];k++)
    {
    for (int l=0;l<=b[4];l++)
    {
    if (i>0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[1+i*1+j*2+k*3+l*4]);
    if (j>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[1+i*1+j*2+k*3+l*4]);
    if (k>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[1+i*1+j*2+k*3+l*4]);
    if (l>0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[1+i*1+j*2+k*3+l*4]);
    }
    }
    }
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]];
    }
    AC40 纪念一下

  • 0
    @ 2015-11-09 19:47:13

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int a[350],b[120],n,m,dpp[40][40][40][40];
    int ka1=0,ka2=0,ka3=0,ka4=0;
    inline int max(int l,int o)
    {
    if(l>o)
    return l;
    return o;
    }
    int dp(int aa)
    {
    int count2,k1=0;
    if(dpp[ka1][ka2][ka3][ka4]!=-1)
    return dpp[ka1][ka2][ka3][ka4];
    if(ka1)
    {
    ka1--;
    k1=dp(aa+1)+a[aa+1];
    ka1++;
    }
    if(ka2)
    {
    ka2--;
    k1=max(k1,dp(aa+2)+a[aa+2]);
    ka2++;
    }
    if(ka3)
    {
    ka3--;
    k1=max(k1,dp(aa+3)+a[aa+3]);
    ka3++;
    }
    if(ka4)
    {
    ka4--;
    k1=max(k1,dp(aa+4)+a[aa+4]);
    ka4++;
    }
    dpp[ka1][ka2][ka3][ka4]=k1;
    return k1;
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    memset(dpp,-1,sizeof(dpp));
    for(int i=0;i<m;i++)
    {
    scanf("%d",&b[i]);
    if(b[i]==1)
    ka1++;
    else if(b[i]==2)
    ka2++;
    else if(b[i]==3)
    ka3++;
    else
    ka4++;
    }
    int k=dp(0)+a[0];
    cout<<k;
    return 0;
    }
    淡定dp+优化

  • 0
    @ 2015-10-03 21:35:58

    四个状态i1,i2,i3,i4代表用的爬行卡数量
    转移方程
    f[i1,i2,i3,i4]:=max(f[i1,i2,i3,i4],
    f[i1-1,i2,i3,i4],f[i1,i2-1,i3,i4],
    f[i1,i2,i3-1,i4],f[i1,i2,i3,i4-1])+
    a[i1+2*i2+3*i3+4*i4+1];

  • 0
    @ 2015-10-02 20:50:47

    /*

    Author : Slience_K
    Belong : C++
    Pro : NOIP 2010 - 2

    */
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n , x , m , a[ 5 ] , d[ 355 ] , f[ 45 ][ 45 ][ 45 ][ 45 ];
    int main(){
    scanf( "%d%d" , &n , &m );
    for( int i = 1 ; i <= n ; i++ )
    scanf( "%d" , &d[ i ] );
    for( int i = 1 ; i <= m ; i++ ){
    scanf( "%d" , &x );
    a[ x ]++;
    }
    int dis , maxn;
    f[ 0 ][ 0 ][ 0 ][ 0 ] = d[ 1 ];
    for( int i = 0 ; i <= a[ 1 ] ; i++ )
    for( int j = 0 ; j <= a[ 2 ] ; j++ )
    for( int k = 0 ; k <= a[ 3 ] ; k++ )
    for( int l = 0 ; l <= a[ 4 ] ; l++ )
    if (( i == 0 )&&( j == 0 )&&( k == 0 )&&( l == 0 )) continue;
    else{
    maxn = 0;
    if (( a[ 1 ] )&&( i >= 1 ))
    maxn = max( maxn , f[ i - 1 ][ j ][ k ][ l ] );
    if (( a[ 2 ] )&&( j >= 1 ))
    maxn = max( maxn , f[ i ][ j - 1 ][ k ][ l ] );
    if (( a[ 3 ] )&&( k >= 1 ))
    maxn = max( maxn , f[ i ][ j ][ k - 1 ][ l ] );
    if (( a[ 4 ] )&&( l >= 1 ))
    maxn = max( maxn , f[ i ][ j ][ k ][ l - 1 ] );
    dis = i + 2 * j + 3 * k + 4 * l + 1;
    maxn += d[ dis ];
    f[ i ][ j ][ k ][ l ] = maxn;
    }
    printf( "%d" , f[ a[ 1 ] ][ a[ 2 ] ][ a[ 3 ] ][ a[ 4 ] ] );
    return 0;
    }

  • 0
    @ 2015-09-28 19:30:36

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    long n,m,i,j,k,l,tmp,score[351]={0},card[5]={0},f[41][41][41][41]={0};
    int main(){
    scanf("%ld%ld",&n,&m);
    for(i=1;i<=n;++i)scanf("%ld",&score[i]);
    for(i=1;i<=m;++i){
    scanf("%ld",&tmp);
    ++card[tmp];
    }
    for(i=0;i<=card[1];++i)
    for(j=0;j<=card[2];++j)
    for(k=0;k<=card[3];++k)
    for(l=0;l<=card[4];++l){
    long tmp1=0,tmp2=0,tmp3=0,tmp4=0;
    if(i)tmp1=f[i-1][j][k][l];
    if(j)tmp2=f[i][j-1][k][l];
    if(k)tmp3=f[i][j][k-1][l];
    if(l)tmp4=f[i][j][k][l-1];
    f[i][j][k][l]=max(max(tmp1,tmp2),max(tmp3,tmp4))+score[i*1+j*2+k*3+l*4+1];
    }
    printf("%ld",f[card[1]][card[2]][card[3]][card[4]]);
    }

  • 0
    @ 2015-09-04 20:31:18

    f[i][j][s][t]=max(f[i-1][j][k][t],f[i][j-1][k][t],f[i][j][k-1][t],f[i][j][k][t-1])+ge[i+j+j+k+k+k+t+t+t+t+1]
    四维动归。。。
    f[i][j][s][t]移动i个一步,j个两步,s个三步,t个四步的最小值
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,m,ge[500],ka[500],f[45][45][45][45],num1,num2,num3,num4;
    int main()
    {
    freopen("tortoise.in","r",stdin);
    freopen("tortoise.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&ge[i]);
    for(int i=1;i<=m;i++){
    scanf("%d",&ka[i]);
    if(ka[i]==1) num1++;
    if(ka[i]==2) num2++;
    if(ka[i]==3) num3++;
    if(ka[i]==4) num4++;
    }
    f[0][0][0][0]=ge[1];
    for(int i=0;i<=num1;i++)
    for(int j=0;j<=num2;j++)
    for(int k=0;k<=num3;k++)
    for(int t=0;t<=num4;t++){
    if(i>0) f[i][j][k][t]=max(f[i-1][j][k][t],f[i][j][k][t]);
    if(j>0) f[i][j][k][t]=max(f[i][j-1][k][t],f[i][j][k][t]);
    if(k>0) f[i][j][k][t]=max(f[i][j][k-1][t],f[i][j][k][t]);
    if(t>0) f[i][j][k][t]=max(f[i][j][k][t-1],f[i][j][k][t]);
    if(i>0||j>0||k>0||t>0) f[i][j][k][t]+=ge[i+j*2+k*3+t*4+1];
    }
    printf("%d",f[num1][num2][num3][num4]);
    }

    • @ 2016-01-23 20:28:10

      仁兄你说的是最小值标里写的是max

  • 0
    @ 2015-08-19 21:08:07

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN = 350+10;

    int a[MAXN], f[41][41][41][41], num[MAXN];

    int main()
    {
    int n, m, b;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
    scanf("%d", &a[i]);
    for(int i=1; i<=m; i++){
    scanf("%d", &b);
    num[b]++;
    }
    f[0][0][0][0] = a[1];
    for(int i=0; i<=num[1]; i++)
    for(int j=0; j<=num[2]; j++)
    for(int k=0; k<=num[3]; k++)
    for(int l=0; l<=num[4]; l++){
    int bri = i + j*2 + k*3 + l*4 + 1;
    if(i>0) f[i][j][k][l] = max(f[i][j][k][l], f[i-1][j][k][l]+a[bri]);
    if(j>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j-1][k][l]+a[bri]);
    if(k>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k-1][l]+a[bri]);
    if(l>0) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l-1]+a[bri]);
    }
    printf("%d", f[num[1]][num[2]][num[3]][num[4]]);
    return 0;
    }
    四维DP

  • 0
    @ 2015-07-07 18:49:57

    P1775乌龟棋
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1775 乌龟棋
    递交时间 2015-07-07 18:48:55
    代码语言 C++
    评测机 VijosEx
    消耗时间 387 ms
    消耗内存 12460 KiB
    评测时间 2015-07-07 18:48:58

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 12460 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 12456 KiB, score = 10

    测试数据 #2: Accepted, time = 31 ms, mem = 12460 KiB, score = 10

    测试数据 #3: Accepted, time = 31 ms, mem = 12460 KiB, score = 10

    测试数据 #4: Accepted, time = 31 ms, mem = 12456 KiB, score = 10

    测试数据 #5: Accepted, time = 31 ms, mem = 12456 KiB, score = 10

    测试数据 #6: Accepted, time = 46 ms, mem = 12460 KiB, score = 10

    测试数据 #7: Accepted, time = 62 ms, mem = 12456 KiB, score = 10

    测试数据 #8: Accepted, time = 78 ms, mem = 12460 KiB, score = 10

    测试数据 #9: Accepted, time = 62 ms, mem = 12460 KiB, score = 10

    Accepted, time = 387 ms, mem = 12460 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>

    using namespace std;

    int n , m;
    int i , j , k , l;
    int a , b , c , d , e;
    int t[350 + 10];
    int f[40 + 2][40 + 2][40 + 2][40 + 2];

    int dp( int x , int y , int z , int w )
    {
    if( f[x][y][z][w] != -1 )
    return f[x][y][z][w];
    if( !x && !y && !z && !w )
    return 0;
    int pos = ( a - x ) * 1 + ( b - y ) * 2 + ( c - z ) * 3 + ( d - w ) * 4 + 1;
    int maxd = 0;
    if( x > 0 )
    maxd = max( maxd , dp( x - 1 , y , z , w ) + t[ pos + 1 ] );
    if( y > 0 )
    maxd = max( maxd , dp( x , y - 1 , z , w ) + t[ pos + 2 ] );
    if( z > 0 )
    maxd = max( maxd , dp( x , y , z - 1 , w ) + t[ pos + 3 ] );
    if( w > 0 )
    maxd = max( maxd , dp( x , y , z , w - 1 ) + t[ pos + 4 ] );
    f[x][y][z][w] = maxd;
    return f[x][y][z][w];
    }

    int main()
    {
    for( i = 0 ; i <= 40 ; i++ )
    for( j = 0 ; j <= 40 ; j++ )
    for( k = 0 ; k <= 40 ; k++ )
    for( l = 0 ; l <= 40 ; l++ )
    f[i][j][k][l] = -1;
    scanf( "%d %d" , &n , &m );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d" , &t[i] );
    for( j = 1 ; j <= m ; j++ )
    {
    scanf( "%d" , &e );
    if( e == 1 )
    a++;
    if( e == 2 )
    b++;
    if( e == 3 )
    c++;
    if( e == 4 )
    d++;
    }
    cout << dp( a , b , c , d ) + t[1] << endl;
    return 0;
    }

  • 0
    @ 2014-10-27 13:38:17

    #include <iostream>
    using namespace std;
    const int INF=100000000;
    int f[350+5];
    int d[350+5][45][45][45];
    bool vis[350+5][45][45][45];
    int dp(int,int,int,int,int);
    int K1,K2,K3,K4;
    int N,M;
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>N>>M;
    for(int i=1;i<=N;++i)
    cin>>f[i];
    for(int i=1;i<=M;++i)
    {
    int t=0;
    cin>>t;
    if(t==1) K1++;
    if(t==2) K2++;
    if(t==3) K3++;
    if(t==4) K4++;
    }
    cout<<dp(N,K1,K2,K3,M-K1-K2-K3)<<endl;

    }
    int dp(int n,int k1,int k2,int k3,int k4)
    {
    if(vis[n][k1][k2][k3]==1) return d[n][k1][k2][k3];
    if(k1<0||k2<0||k3<0||k4<0) return -INF;
    if(n==1) return f[1];
    if(n<1) return -INF;
    vis[n][k1][k2][k3]=1;
    if(dp(n-1,k1-1,k2,k3,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-1,k1-1,k2,k3,k4)+f[n];
    if(dp(n-2,k1,k2-1,k3,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-2,k1,k2-1,k3,k4)+f[n];
    if(dp(n-3,k1,k2,k3-1,k4)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-3,k1,k2,k3-1,k4)+f[n];
    if(dp(n-4,k1,k2,k3,k4-1)+f[n]>d[n][k1][k2][k3]) d[n][k1][k2][k3]=dp(n-4,k1,k2,k3,k4-1)+f[n];
    return d[n][k1][k2][k3];
    }

  • 0
    @ 2014-10-26 23:08:35

    见过最水的DP,我这种蒟蒻居然能自己写出状态转移方程~~
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<string>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<cmath>
    #include<cctype>
    #define FOR(a,b) for(int i=a;i<=b;i++)
    using namespace std;
    int N,M,tmp;
    int d[41][41][41][41];
    int a[5];
    int b[351];
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>N>>M;
    FOR(0,N-1) cin>>b[i];
    FOR(1,M)
    {
    cin>>tmp;
    a[tmp]++;
    }
    d[0][0][0][0]=b[0];
    for(int i=0;i<=a[1];i++)
    for(int j=0;j<=a[2];j++)
    for(int k=0;k<=a[3];k++)
    for(int l=0;l<=a[4];l++)
    {
    tmp=i+2*j+3*k+4*l;
    if(i) d[i][j][k][l]=max(d[i][j][k][l],d[i-1][j][k][l]+b[tmp]);
    if(j) d[i][j][k][l]=max(d[i][j][k][l],d[i][j-1][k][l]+b[tmp]);
    if(k) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k-1][l]+b[tmp]);
    if(l) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k][l-1]+b[tmp]);
    }
    cout<<d[a[1]][a[2]][a[3]][a[4]]<<endl;
    return 0;
    }

  • 0
    @ 2014-10-21 21:15:00

    记忆化搜索可以排除冗余的状态

  • 0
    @ 2014-10-15 16:29:41

    #include<iostream>
    #include<fstream>
    #include<cstring>

    using namespace std;

    inline int update(int &a,int b)
    {
    a=a>b?a:b;
    }

    int N,M,map[351],count[5],f[41][41][41][41],ans=0;

    int main()
    {
    ifstream cin("tortoise.in");
    ofstream cout("tortoise.out");
    memset(f,0,sizeof(f));
    memset(count,0,sizeof(count));
    cin>>N>>M;
    for(int i=1;i<=N;i++)
    cin>>map[i];
    for(int i=1,card;i<=M;i++)
    {
    cin>>card;
    count[card]++;
    }
    f[0][0][0][0]=map[1];
    for(int i=0,now;i<=count[1];i++)
    {
    now=1+i;
    if (now>N) break;
    for(int j=0;j<=count[2];j++)
    {
    now=1+i+(j<<1);
    if (now>N) break;
    for(int k=0;k<=count[3];k++)
    {
    now=1+i+(j<<1)+k*3;
    if (now>N) break;
    for(int l=0;l<=count[4];l++)
    {
    int now=1+i+(j<<1)+k*3+(l<<2);
    if (now>N) break;
    if (i>0) update(f[i][j][k][l],f[i-1][j][k][l]+map[now]);
    if (j>0) update(f[i][j][k][l],f[i][j-1][k][l]+map[now]);
    if (k>0) update(f[i][j][k][l],f[i][j][k-1][l]+map[now]);
    if (l>0) update(f[i][j][k][l],f[i][j][k][l-1]+map[now]);
    if (now==N) ans=max(ans,f[i][j][k][l]);
    }
    }
    }
    }
    cout<<ans<<endl;
    return 0;
    }

信息

ID
1775
难度
2
分类
动态规划 点击显示
标签
递交数
2272
已通过
1259
通过率
55%
被复制
8
上传者