dp FAQ

#include 
#include 
using namespace std;

int a[105][105];
int dp[105][105];

int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                cin>>a[i][j];
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
            }
        }
        int ans=-1;
        for(int i=1;i<=n;i++)
        {
            if(anscout<return 0;
}

#include 
#include 
using namespace std;

int a[105][105];
int dp[105];

int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        dp[i]=a[n][i];
        for(int i=n-1;i>=0;i--)
        {
            for(int j=1;j<=i;j++)
            {
                dp[j]=max(dp[j],dp[j+1])+a[i][j];
            }
        }
        cout<1]<return 0;
}

#include 
#include 
#include 
using namespace std;

const int maxn=10005;

int a[maxn];
int dp[maxn];
int pos[maxn];//pos[i], i        
int n;

int main()
{
    while(cin>>n&&n)
    {
        memset(dp,0,sizeof(dp));
        memset(pos,0,sizeof(pos));
        for(int i=0;icin>>a[i];
        int ans=-1;
        for(int i=0;iif(dp[i-1]<=0)
            pos[i]=a[i];
            else
            pos[i]=pos[i-1];
            dp[i]=max(a[i],dp[i-1]+a[i]);
            ans=max(ans,dp[i]);
        }
        if(ans<0)
        {
            printf("0 %d %d
",a[0],a[n-1]);
            continue;
        }
        for(int i=0;iif(dp[i]==ans)
            {
                printf("%d %d %d
",dp[i],pos[i],a[i]);
                break;
            }
        }
    }
    return 0;
}

#include 
#include 
#include 
using namespace std;

const int maxn=100005;

int a[maxn];
int dp[maxn];
int pos[maxn];

int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        memset(dp,0,sizeof(dp));
        memset(pos,0,sizeof(pos));
        int n;
        int ans=-100000000;
        scanf("%d",&n);
        for(int i=0;i"%d",&a[i]);
        for(int i=0;iif(dp[i-1]<0)
            pos[i]=i;
            else
            pos[i]=pos[i-1];
            dp[i]=max(dp[i-1]+a[i],a[i]);
            ans=max(ans,dp[i]);
        }
        for(int i=0;iif(ans==dp[i])
            {
                printf("Case %d:
",cas);
                printf("%d %d %d
",ans,pos[i]+1,i+1);
            }
        }
        if(cas!=t)
        printf("
");
    }
    return 0;
}

1.   ai    ;  2.   j<i aj[i]=max{1,dp[j]+1|j 

#include  
#include  
#include  
using namespace std;  
int a[10010];  
int dp[10010];  
int main()  
{  
    int n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(int i=0;iscanf("%d",&a[i]);  
            dp[i]=1;  
        }  
        int ans=0;  
        for(int i=1;ifor(int j=0;jif(a[j]1,dp[i]);  
}  
}  
ans=max(ans,dp[i]);  
}  
printf("%d",ans);  
}  
return 0;  
}

#include  
#include  
#include  
using namespace std;  
#define INF 0x3f3f3f  
int dp[10010];//dp[i]     i+1           ；   
int a[10010];  
int main()  
{  
    int n;  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(int i=0;iscanf("%d",&a[i]);  
            dp[i]=INF;//    memset     INF,    0 -1；  
                      //   fill(dp,dp+n,INF);   
        }  
        for(int i=0;i//  >=a[i]      ，  a[i]  ；   
        }  
        printf("%d
",lower_bound(dp,dp+n,INF)-dp);//     INF                  ；   
    }  
    return 0;  
}  

#include 
#include 

using namespace std;

const int maxn=1010;

int a[maxn];
int dp[maxn];

int main()
{
    int n;
    while(scanf("%d",&n)!=-1)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(a[i]>a[j])
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
    return 0;
}

#include
#include
#include
using namespace std;

char a[1005],b[1005];
int dp[1005][1005];

int main()
{
    while(cin>>a>>b)
    {
        int len1=strlen(a);
        int len2=strlen(b);
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=len1; i++)
            for(int j=1; j<=len2; j++)
            {
                if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        cout<return 0;
}

#include 
#include 
using namespace std;

int dp[400][400];

void LPS(char s[],int len)
{
    for(int i=len-1;i>=0;i--)
    {
        dp[i][i]=1;
        for(int j=i+1;jif(s[i]==s[j])
            dp[i][j]=dp[i+1][j-1]+2;
            else
            dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
        }
    }
}
int main()
{
    char s[305];
    while(cin>>s)
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        LPS(s,len);
        cout<0][len-1]<return 0;
}