Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:三维dp难道不可以?

Posted by 13926491 at 2016-05-21 21:17:45 on Problem 3661
In Reply To:三维dp难道不可以? Posted by:ZCJ at 2015-04-27 09:14:55
我也用的三维dp,ac了
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
int a[10000+10];
int dp[10000+10][505][2]={0};
int xu[10000+10]={0};
int main()
{
    //freopen("F://input.txt","r",stdin);
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
{
    int i,q,w,l;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
    {
        int t=i>k?k:i;
        for(q=1;q<=t;q++)
        {
           dp[i][q][1]=dp[i-1][q-1][1]+a[i];
           if(q==1)dp[i][q][1]=max(dp[i][q][1],dp[i-1][0][0]+a[i]);
        }
        for(q=0;q<=t;q++)
        {
            if(q==0)
            {
                dp[i][q][0]=max(dp[i-1][q][0],dp[i-1][q+1][1]);
                dp[i][q][0]=max(dp[i-1][q+1][0],dp[i][q][0]);
            }
            else
            dp[i][q][0]=max(dp[i-1][q+1][0],dp[i-1][q+1][1]);
        }
    }

    printf("%d\n",dp[n][0][0]);
}
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator