//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
if (nums.size() == 0)
return vector<int>({-1, -1});
int l = 0,r = nums.size()-1;
while(l<r){
int mid = (l+r)/2;
if(nums[mid]>=target) r= mid;
else l = mid+1;
}
if (nums[l] != target)
return vector<int>({-1, -1});
res.push_back(l);
l = 0,r = nums.size()-1;
while(l<r){
int mid = (l+r)/2;
if(nums[mid]<=target)l=mid+1;
else r = mid;
}
if (nums[l] > target)
res.push_back(l-1);
else
res.push_back(l);
return res;

}
};


### 题目描述

#### 样例

输入: 4



输入: 8

由于返回类型是整数，小数部分将被舍去。


### 算法1

#### C++ 代码

class Solution {
public:
int mySqrt(int x) {
long l = 0, h = (long)x + 1;
while(l < h){
long m = (l + h) / 2;
if(m * m > x) h = m; else l = ++m;
}
return (int)l - 1;
}
};


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0,r = nums.size()-1;
if(r==-1) return 0;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < target)
l = mid + 1;
else
r = mid;
}

if (nums[l] >= target)
return l;

return nums.size();
}
};


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
int mySqrt(int x) {
long l = 0, h = (long)x + 1;
while(l < h){
long m = (l + h) / 2;
if(m * m > x) h = m; else l = ++m;
}
return (int)l - 1;
}
};


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 301
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int s[N],f[N][N];
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++)cin>>s[i];
for(int i = 1;i<=n;i++)s[i]+=s[i-1];
for (int len = 2; len <= n; len++)           //区间长度
for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
int j = i + len - 1;  //区间终点
f[i][j] = 1e8;
for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
}
}

cout<<f[1][n]<<endl;
return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/*

1.状态表示 f（n，m）表示字符串A中前n个字符，B中前m个字符的所有公共子序列
2.状态计算：分成4个状态，1.A[i],B[j]都不选，这个情况在2,3种情况中被包含，所有不用计算
2.A[i]选B[j]不选，f[i][j-1]
3.A[i]不选B[j]选，f[i-1][j]
4.都选 f[i-1][j-1]+1 条件：A[i]==B[j]
3.状态转移方程：f[i][j] = max(f[i-1][j],f[i][j-1])   if(A[i]==B[j])  f[i][j] = max(f[i][j],f[i-1][j-1]+1)
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 1010
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
char A[N],B[N];
int f[N][N];
int main()
{
int n,m;
cin>>n>>m;
cin>>A+1>>B+1;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++){
f[i][j] = max(f[i-1][j],f[i][j-1]);
if(A[i]==B[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][m]<<endl;
return 0;
}



#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 100005
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
vector<int> stk;
int a[N],dp[N];
int main()
{
int n;
cin>>n;
for(int i =1;i<=n;i++)cin>>a[i];
stk.push_back(a[1]);
for(int i =1;i<=n;i++){
if(a[i]>stk.back()){
stk.push_back(a[i]);
}
else{
*lower_bound(stk.begin(),stk.end(),a[i])=a[i];
}
}
cout<<stk.size()<<endl;
return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 1010
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int dp[N],a[N];
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++){
dp[i] = 1;
cin>>a[i];
for(int j = 1;j<=i-1;j++){
if(a[i]>a[j]){
dp[i] = max(dp[i],dp[j]+1);
}
}
}
int res = 1;
for(int i = 1;i<=n;i++)
res = max(res,dp[i]);
cout<<res<<endl;
return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 505
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int f[N][N],dp[N][N];
int main()
{
int n;
cin>>n;
for(int i = 0;i<n;i++)
for(int j = 0;j<=i;j++){
cin>>f[i][j];
if(j==0)dp[i][j] = dp[i-1][j]+f[i][j];
else if(j==i)dp[i][j] = dp[i-1][j-1]+f[i][j];
else
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])+f[i][j];
}
int res = -INF;
for(int i=0;i<n;i++ ) res = max(res,dp[n-1][i]);
cout<<res<<endl;
return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<map>
#include<cmath>
#define INF 0x7f7f7f7f
#define N 2500
typedef long long ll;
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const ll mo = 998244353;
int s[N],w[N][N],v[N][N];
int dp[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++) {
cin>>s[i];
for(int j = 0;j<s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i = 1;i<=n;i++)
for(int j = m;j>=0;j--)
for(int k = 0;k<s[i];k++)
if(j>=v[i][k])
dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k]);
cout<<dp[m]<<endl;
return 0;
}