問題描述

圖1 問題描述1

圖2 問題描述2

解題思路

找子問題

圖3 解題思路1

圖4 解題思路2

確定狀態(tài)

圖5 解題思路3

確定狀態(tài)轉(zhuǎn)移方程

圖6 解題思路4

程序?qū)崿F(xiàn)

人人為我

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1000;
int s[MAXN];
int f[MAXN];
int n;

int main()
{
    cin >> n;
    memset(s, 0, sizeof(s));//一個字節(jié)一個字節(jié)地填充
    memset(f,0,sizeof(f));
    for(int i = 0; i < n; i++){
        cin >> s[i];
        f[i]=1;}
    //人人為我
    for(int i = 1; i < n; i++)
        for(int j = 0; j < i; j++)
            if(s[j] < s[i]) f[i] = max(f[i], f[j] + 1);
    cout <<*max_element(f,f+n)<< endl;
    return 0;
}

我為人人

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1000;
int s[MAXN];
int f[MAXN];
int n;

int main()
{
    cin >> n;
    memset(s, 0, sizeof(s));//一個字節(jié)一個字節(jié)地填充
    memset(f,0,sizeof(f));
    for(int i = 0; i < n; i++){
        cin >> s[i];
        f[i]=1;}
    //我為人人
    for(int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if(s[i] < s[j]) f[j] = max(f[j], f[i] + 1);
    cout <<*max_element(f,f+n)<< endl;
    return 0;
}

運(yùn)行結(jié)果

人人為我

圖7 運(yùn)行結(jié)果1

我為人人

圖8 運(yùn)行結(jié)果2