A:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N];
int f[N];
int cnt;
int main(void)
{
cin >> n;
for(int i = 1;i <= n; i ++) cin >> a[i];
f[0] = 0;
f[1] = a[1];cnt = 1;
for(int i = 2; i <= n; i++)
{
int left = 1, right = cnt;
int res = -1;
while(left <= right)
{
int mid = (left + right) / 2;
if(f[mid] >= a[i])
{
res = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
if(res == -1)
{
cnt++;
f[cnt] = a[i];
}
else
{
f[res] = a[i];
}
}
cout << cnt << endl;
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int to[2000]={0};
int a[2000];
int d[2000];
for(int i=1;i<=n;i++)
{
cin>>a[i];
d[i]=a[i];
}
int v,u;
bool vis[2000][2000];
while(1)
{
cin>>v>>u;
if(v0&&u0) break;
vis[v][u]=true;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(vis[i][j]&&d[j]<d[i]+a[j])
{
d[j]=d[i]+a[j];
to[j]=i;
}
}
}
int maxx=0;
int k;
for(int i=1;i<=n;i++)
{
if(d[i]>maxx)
{
maxx=d[i];
k=i;
}
}
int print[2000];
print[0]=k;
int print_size=1;
for(int i=1;;i++)
{
if(to[k]==0) break;
print[i]=to[k];
k=to[k];
print_size++;
}
for(int i=print_size-1;i>=0;i--)
{
if(i>0) cout<<print[i]<<"-";
else cout<<print[i];
}
cout<<endl;
cout<<maxx;
return 0;
}
C
#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
int a[maxn],dp[maxn],s[maxn],n=0,k,ans;
int main(){
ios::sync_with_stdio(0);
while(cin>>k)a[++n]=k;
for(int i=1;i<=n;++i){
dp[i]=1;
int l=0,r=ans+1;
while(r-l>1){
int mid=(l+r)>>1;
if(s[mid]>=a[i]){
l=mid;
}
else {
r=mid;
}
}
dp[i]=l+1;
s[dp[i]]=a[i];
ans=max(ans,dp[i]);
}
cout<<ans<<endl;ans=0;
memset(s,0,sizeof(s));
for(int i=1;i<=n;++i){
dp[i]=1;
int l=0,r=ans+1;
while(r-l>1){
int mid=(l+r)>>1;
if(s[mid]<a[i]){
l=mid;
}
else {
r=mid;
}
}
dp[i]=l+1;
s[dp[i]]=a[i];
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}D
#include
using namespace std;
const int N=5*1e5+5; int a[N], f[N], ans;
int main() { int n; cin>>n; for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) { int mx = 0; for(int j=1; j<i; j++) { if(a[j] < a[i]) mx = max(mx, f[j]); } f[i] = mx + 1; }
for(int i=1; i<=n; i++) ans = max(ans, f[i]); cout<<"Max="<<ans<<endl; return 0; }E #include <bits/stdc++.h> using namespace std; const int N = 1005; int n, cost[N]; int dp[N]; int f(int k) { if (k == 0 || k == 1) return dp[k] = 0; if (dp[k] != -1) return dp[k]; return dp[k] = min(f(k - 1) + cost[k - 1], f(k - 2) + cost[k - 2]); } void bright(void) { cout << f(n) << endl; } void light(void) { ios::sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) cin >> cost[i]; for (int i = 2; i <= n; i++) dp[i] = -1; } int main(void) { light(); bright(); return 0; } F #include<bits/stdc++.h> using namespace std; const int N=1010; int n; int a[N][N]; int main(){ cin>>n; for(int i = 1; i <= n; i ++) for(int j = 1; j <= i; j ++) cin >> a[i][j]; for(int i = n; i >= 1; i--) for(int j = i; j >= 1; j--) a[i][j]+=max(a[i+1][j],a[i+1][j+1]); cout << a[1][1]; return 0; } G #include<bits/stdc++.h> using namespace std; int n,a[110],dp[110]; int main() { cin>>n; for (int i=1;i<=n;i++) { cin>>a[i]; } dp[1]=a[1]; dp[2]=max(a[1],a[2]); for (int i=3;i<=n;i++) { dp[i]=max(dp[i-1],dp[i-2]+a[i]); } int t=0; for (int i=1;i<=n;i++) { t=max(t,dp[i]); } cout<<t; return 0; } H #include using namespace std; const int N=2*1e6+10; long long n,a[N],f[N],ans=-0x3f3f3f3f; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) f[i]=max(f[i-1]+a[i],a[i]); for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans<<endl; return 0; } I #include<bits/stdc++.h> using namespace std; const int maxn=100050; int a[maxn],dp[maxn],s[maxn],n=0,k,ans; int main(){ ios::sync_with_stdio(0); while(cin>>k)a[++n]=k; for(int i=1;i<=n;++i){ dp[i]=1; int l=0,r=ans+1; while(r-l>1){ int mid=(l+r)>>1; if(s[mid]>=a[i]){ l=mid; } else { r=mid; } } dp[i]=l+1; s[dp[i]]=a[i]; ans=max(ans,dp[i]); } cout<<ans<<endl;ans=0; memset(s,0,sizeof(s)); for(int i=1;i<=n;++i){ dp[i]=1; int l=0,r=ans+1; while(r-l>1){ int mid=(l+r)>>1; if(s[mid]<a[i]){ l=mid; } else { r=mid; } } dp[i]=l+1; s[dp[i]]=a[i]; ans=max(ans,dp[i]); } // cout<<ans<<endl; return 0; }
