问题描述
图1 问题描述1
图2 问题描述2
解题思路
找子问题
图3 解题思路1
图4 解题思路2
确定状态
图5 解题思路3
确定状态转移方程
图6 解题思路4
程序实现
人人为我
#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));//一个字节一个字节地填充
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));//一个字节一个字节地填充
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;
}
运行结果
人人为我
图7 运行结果1
我为人人
图8 运行结果2
