杭州网站设计优异柚v米科技,爱站网备案查询,中国营销,wordpress文章有模板个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【AcWing算法提高学习专栏】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望对大家… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【AcWing算法提高学习专栏】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 目录 一、AcWing1017.怪盗基德的滑翔翼解题代码 二、AcWing1014.登山解题代码 三、AcWing482.合唱队形解题代码 一、AcWing1017.怪盗基德的滑翔翼
原题链接点击直接跳转到该题目
解题代码
#includeiostream
#includevector
using namespace std;const int N 110;
int arr[N];int main()
{int K;cin K;while(K--){int res 1;int n;scanf(%d,n);for(int i 1;i n;i) scanf(%d,arr[i]);//创建dp表vectorint dp1(N,1);//正向求解for(int i 2;i n;i){for(int j 1;j i;j)if(arr[i] arr[j]) dp1[i] max(dp1[i],dp1[j] 1);res max(dp1[i],res);}//反向求解vectorint dp2(N,1);for(int i n - 1;i 1;i--){for(int j n;j i;j--)if(arr[j] arr[i]) dp2[i] max(dp2[i],dp2[j] 1);res max(dp2[i],res);}printf(%d\n,res);}return 0;
}二、AcWing1014.登山
原题链接点击直接跳转到该题目
解题代码
#includeiostream
#includevector
using namespace std;const int N 1010;
int arr[N];int main()
{int n;scanf(%d,n);for(int i 1;i n;i) cin arr[i];// 创建dp表vectorint dp1(N,1),dp2(N,1);for(int i 2;i n;i){for(int j 1;j i;j){if(arr[i] arr[j]) dp1[i] max(dp1[i],dp1[j] 1);}}for(int i n - 1;i 1;i--){for(int j n;j i;j--){if(arr[i] arr[j]) dp2[i] max(dp2[i],dp2[j] 1);}}vectorint dp(N);int ret 0;for(int i 1;i n;i){dp[i] dp1[i] dp2[i] - 1;ret max(ret,dp[i]);}printf(%d\n,ret);return 0;
}三、AcWing482.合唱队形
原题链接点击直接跳转到该题目
解题代码
#includeiostream
#includevector
using namespace std;const int N 110;
int arr[N];int main()
{int n;scanf(%d,n);for(int i 1;i n;i) scanf(%d,arr[i]);// 创建dp表vectorint dp1(N,1),dp2(N,1);for(int i 2;i n;i){for(int j 1;j i;j){if(arr[i] arr[j]) dp1[i] max(dp1[i],dp1[j] 1);}}for(int i n - 1;i 1;i--){for(int j n;j i;j--){if(arr[i] arr[j]) dp2[i] max(dp2[i],dp2[j] 1);}}vectorint dp(N);int res 0;for(int i 1;i n;i) dp[i] dp1[i] dp2[i] - 1,res max(res,dp[i]);printf(%d\n,n - res);return 0;
}
