个人网站建设一般流程,网络营销文案策划,正规营销型网站建设,wordpress 博客搭建文章目录
接龙数列冶炼金属 一、接龙数列OJ链接
本题思路:本题是一道经典的dp问题#xff0c;设第i个数的首位数字是first#xff0c; 末位数字是last。因为第i个数只可能加到一个以first结尾的接龙数列中使得这个接龙数列长度加1并且结尾数字变成last.所以状态转移方程为d… 文章目录
接龙数列冶炼金属 一、接龙数列OJ链接
本题思路:本题是一道经典的dp问题设第i个数的首位数字是first 末位数字是last。因为第i个数只可能加到一个以first结尾的接龙数列中使得这个接龙数列长度加1并且结尾数字变成last.所以状态转移方程为dp[i][last] max(dp[i - 1][last], dp[i - 1][first] 1)而显然第一维可以优化掉。
#include bits/stdc.hconstexpr int N1e510;int n;
int dp[N][10];//表示前i个数以j结尾最小删除的个数/*
设第i个数的首位数字是first 末位数字是last。
因为第i个数只可能加到一个以first结尾的接龙数列中
使得这个接龙数列长度加1并且结尾数字变成last.
所以状态转移方程为dp[i][last] max(dp[i - 1][last], dp[i - 1][first] 1)
而显然第一维可以优化掉。
*/int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cinn;for(int i1;in;i){std::string num;std::cinnum;int firstnum[0]-0,lastnum[num.size()-1]-0;for(int j0;j10;j){if(jlast)dp[i][j]std::min(dp[i-1][first],dp[i-1][last]1);elsedp[i][j]dp[i-1][j]1;}}int resINT_MAX;for(int i0;i10;i) resstd::min(res,dp[n][i]);std::coutresstd::endl;return 0;
}
二、冶炼金属OJ链接
本题思路:本题是一道数学的题目设答案为v,因为能炼出b个但炼不出b1个所以有b×v≤a且a(b1)×v即 ab1v⩽ab最小值 ab11, 最大值ab。
#include bits/stdc.hint main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;int mi 0 , mx 2e9 ; std::cinn;for(int i 1 ; i n ; i ){int a , b ; std::cin a b ; int r a/b , l a/(b1)1;mi std::max(mi , l);mx std::min(mx , r) ; }std::cout mi mx std::endl ; return 0;
}
