头像

饮者




离线:2天前


活动打卡代码 AcWing 187. 导弹防御系统

饮者
27天前
#include <bits/stdc++.h>
using namespace std;
#define MaxN 55
#define INF 0x3f3f3f3f
int A[MaxN],Up[MaxN],Down[MaxN],n,ans;
void solve(int cnt,int su,int sd){
    if( su + sd >= ans ) return ;
    if( cnt >= n ){
        ans=min(ans,su+sd);
        return ;
    }
    //将A[cnt]放置于上升子序列当中
    int i=0;
    while( i < su && Up[i] >= A[cnt] ) i++;
    if( i < su ){
        int temp=Up[i];
        Up[i]=A[cnt];
        solve(cnt+1,su,sd);
        Up[i]=temp;
    }
    else{
        Up[i]=A[cnt];
        solve(cnt+1,su+1,sd);
    }
    //将A[cnt]放置于下降子序列当中 
    int j=0;
    while( j < sd && Down[j] <= A[cnt] ) j++;
    if( j < sd ){
        int temp=Down[j];
        Down[j]=A[cnt];
        solve(cnt+1,su,sd);
        Down[j]=temp;
    }
    else{
        Down[j]=A[cnt];
        solve(cnt+1,su,sd+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    while( cin >> n && n ){
        ans=INF;
        for(int i=0; i<n; i++) cin >> A[i];
        solve(0,0,0);
        cout << ans << '\n';
    }
    return 0;
}



活动打卡代码 AcWing 1010. 拦截导弹

饮者
27天前

详细题解

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MaxN 100010
int A[MaxN],dp[MaxN];
signed main(){
    ios::sync_with_stdio(false);
    int cnt=0,ans=-1;
    while( cin >> A[++cnt] ) ; 
    cnt--;
    for(int i=cnt; i>=1; i--){
        dp[i]=1;
        for(int j=cnt; j>i; j--){
            if( A[j] <= A[i] ){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout << ans << '\n';
    ans=-1;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=cnt; i++){
        dp[i]=1;
        for(int j=1; j<i; j++){
            if( A[j] < A[i] ){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout << ans << '\n';
    return 0;
} 


活动打卡代码 AcWing 1012. 友好城市

饮者
30天前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 5010
#define PII pair<int,int>
PII A[MaxN];
int dp[MaxN];
signed main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i].first >> A[i].second;
        dp[i]=1;
    }
    sort(A+1,A+1+n);
    int ans=-1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            if( A[j].second < A[i].second ){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout << ans <<'\n';
    return 0;
} 



饮者
30天前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010
int A[MaxN],dp[MaxN];
signed main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
        dp[i]=A[i];
    }
    int ans=-1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            if( A[j] < A[i] ){
                dp[i]=max(dp[i],dp[j]+A[i]);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout << ans <<'\n';
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

饮者
30天前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010
int A[MaxN],Up[MaxN],Down[MaxN];
void solve(int n){
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            if( A[j] < A[i] ){
                Up[i]=max(Up[i],Up[j]+1);
            }
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=n; j>i; j--){
            if( A[j] < A[i] ){
                Down[i]=max(Down[i],Down[j]+1);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
        Up[i]=Down[i]=1;
    }
    solve(n);
    int ans=-1;
    for(int i=1; i<=n; i++){
        ans=max(ans,Up[i]+Down[i]-1);
    }
    cout << n-ans <<'\n';
    return 0;
}


活动打卡代码 AcWing 1014. 登山

饮者
30天前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010
int A[MaxN],Up[MaxN],Down[MaxN];
void solve(int n){
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            if( A[j] < A[i] ){
                Up[i]=max(Up[i],Up[j]+1);
            }
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=n; j>i; j--){
            if( A[j] < A[i] ){
                Down[i]=max(Down[i],Down[j]+1);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
        Up[i]=Down[i]=1;
    }
    solve(n);
    int ans=-1;
    for(int i=1; i<=n; i++){
        ans=max(ans,Up[i]+Down[i]-1);
    }
    cout << ans <<'\n';
    return 0;
}



饮者
1个月前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010
#define INF 0x3f3f3f3f
int A[MaxN],dp[MaxN],n;
void solve(){
    for(int i=1; i<=n; i++) dp[i]=1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            if( A[j] < A[i] ){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
}
void _solve(){
    for(int i=1; i<=n; i++) dp[i]=1;
    for(int i=n; i>=1; i--){
        for(int j=n; j>i; j--){
            if( A[j] < A[i] ){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while( T-- ){
        cin >> n;
        for(int i=1; i<=n; i++) cin >> A[i];
        solve();
        int ans=-INF;
        for(int i=1; i<=n; i++) ans=max(ans,dp[i]);
        _solve();
        for(int i=1; i<=n; i++) ans=max(ans,dp[i]);
        cout <<  ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 275. 传纸条

饮者
1个月前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 55
typedef long long LL;
int A[MaxN][MaxN];
LL dp[MaxN][MaxN][MaxN][MaxN];
signed main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> A[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int u=1; u<=n; u++){
                for(int v=1; v<=m; v++){
                    dp[i][j][u][v]=max(dp[i-1][j][u-1][v],max(dp[i-1][j][u][v-1],max(dp[i][j-1][u-1][v],dp[i][j-1][u][v-1])))+A[i][j];
                    if( i != u && j != v ){
                        dp[i][j][u][v]+=A[u][v];
                    }
                }
            }
        }
    }
    cout << dp[n][m][n][m];
    return 0;
} 


活动打卡代码 AcWing 1027. 方格取数

饮者
1个月前
#include <bits/stdc++.h>
using namespace std;
#define MaxN 15
int A[MaxN][MaxN],dp[MaxN][MaxN][MaxN][MaxN];
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int x,y,C;
    while( cin>>x>>y>>C && x && y && C ){
        A[x][y]=C;
    }
    for(int i=1; i<=n ;i++){
        for(int j=1; j<=n ;j++){
            for(int u=1; u<=n; u++){
                for(int v=1; v<=n; v++){
                    dp[i][j][u][v]=max(dp[i-1][j][u-1][v],max(dp[i-1][j][u][v-1],max(dp[i][j-1][u-1][v],dp[i][j-1][u][v-1])))+A[i][j];
                    if( i != u && j != v ){
                        dp[i][j][u][v]+=A[u][v];
                    }
                }
            }
        }
    }
    cout<<dp[n][n][n][n];
    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

饮者
1个月前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 105 
int A[MaxN][MaxN],dp[MaxN][MaxN];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
signed main(){
    ios::sync_with_stdio(false);
    memset(dp,0x3f,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>A[i][j];
        }
    }
    dp[1][1]=A[1][1];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if( i == 1 && j == 1 ) continue;
            for(int k=0; k<4; k++){
                dp[i][j]=min(dp[i][j],dp[i+dir[k][0]][j+dir[k][1]]+A[i][j]);
            }
        }
    }
    cout<<dp[n][n];
    return 0;
}