제출 #173290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173290		DeD_TihoN	Bootfall (IZhO17_bootfall)	C++14	0 / 100	26 ms	24184 KiB

bootfall

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=1000+7;
const int inf=1e18+1e9;
const int mod=1e9+7;
const ld eps=1e-9;

int a[N];
int dp[N][N];
bool used[N][N];
vector< vector<int> >b[N][N];

int get_dp(int l,int r)
{
    if (l>r){
        return 0;
    }
    if (used[l][r]){
        return dp[l][r];
    }
    used[l][r]=true;
    dp[l][r]=inf;
    if (l==r){
        dp[l][r]=1;
    }
    else {
        for (int j=l;j<r;++j){
            dp[l][r]=min(dp[l][r],get_dp(l,j)+get_dp(j+1,r));
        }
        for (int j=0;j<b[l][r].size();++j){
            vector<int>d=b[l][r][j];
            int res=0;
            int last=l-1;
            for (int k=0;k<d.size();++k){
                res+=get_dp(last+1,d[k]-1);
                last=d[k];
            }
            res+=get_dp(last+1,r);
            dp[l][r]=min(dp[l][r],res+1);
        }
    }
    return dp[l][r];
}

main ()
{
    ios;
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    for (int i=1;i<=n;++i){
        int r=i+1;
        vector<int>c;
        c.pb(a[i]);
        while(r<=n && a[r]>a[r-1]){
            c.pb(a[r]);
            b[a[i]][a[r]].pb(c);
            ++r;
        }
    }
    cout<<get_dp(1,n)<<endl;
}

//8
//1 3 4 2 5 7 8 6

컴파일 시 표준 에러 (stderr) 메시지

bootfall.cpp: In function 'long long int get_dp(long long int, long long int)':
bootfall.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<b[l][r].size();++j){
                      ~^~~~~~~~~~~~~~~
bootfall.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k=0;k<d.size();++k){
                          ~^~~~~~~~~
bootfall.cpp: At global scope:
bootfall.cpp:75:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35