题目

问题描述
　　A同学的学习成绩十分不稳定，于是老师对他说：“只要你连续4天成绩有进步，那我就奖励给你一朵小红花。”可是这对于A同学太困难了。于是，老师对他放宽了要求：“只要你有4天成绩是递增的，我就奖励你一朵小红花。”即只要对于第i、j、k、l四天，满足i<j<k<l并且对于成绩wi<wj<wk<wl，那么就可以得到一朵小红花的奖励。现让你求出，A同学可以得到多少朵小红花。
输入格式
　　第一行一个整数n，表示总共有n天。第二行n个数，表示每天的成绩wi。
输出格式
　　一个数，表示总共可以得到多少朵小红花。
样例输入
6
1 3 2 3 4 5
样例输出
6
数据规模和约定
　　对于40%的数据，n<=50；
　　对于100%的数据，n<=2000，0<=wi<=109。

分析问题

数位DP，与省赛模拟题类似

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
int n, score[2001];
LL dp[2001][4];
LL dfs(int pos, int preDay){	//已经填完pos位，前一位是第几天 
	if(pos == 4)
		return 1;
	if(dp[preDay][pos] != -1)
		return dp[preDay][pos];
	LL cnt = 0;
	for(int i = preDay + 1; i <= n; i++){
		if(score[i] > score[preDay])
			cnt += dfs(pos + 1, i);
	}
	dp[preDay][pos] = cnt;
	return cnt;
}
int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &score[i]);
	LL ans = 0;
	for(int i = 1; i <= n - 3; i++){
		ans += dfs(1, i);
	}
	printf("%I64dn", ans);
 	return 0;
}

最后

以上就是闪闪高山为你收集整理的蓝桥OJ 算法提高 天天向上题目分析问题代码的全部内容，希望文章能够帮你解决蓝桥OJ 算法提高 天天向上题目分析问题代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。