头像

墨羽魂韶


访客:866

离线:9小时前



墨羽魂韶
17小时前
#include "iostream"
#include "vector"
using namespace std;

//#define __test
#define __defi
//#define __loop

#ifdef __defi
inline int read()
{
    int ans = 0, mark = 1;
    int t = getchar();
    while(t < '0' || t > '9'){
        if (t == '-') mark = -1;
        t = getchar();
    }
    while(t <= '9' && t >= '0'){
        ans = (ans << 3) + (ans << 1) + t - '0';
        t = getchar();
    }
    return ans * mark;
}


inline void write( __int128 x ) {
    char F[ 2000 ] ;
    __int128 tmp = x > 0 ? x : -x ;
    if( x < 0 ) putchar( '-' ) ;
    int cnt = 0 ;
       while( tmp > 0 ) {
           F[ cnt ++ ] = tmp % 10 + '0' ;
           tmp /= 10 ;
       }
       while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}

#define in(a) a=read()
#define inn(a, b) in(a), in(b)
#define innn(a, b, c) in(a), in(b), in(c)
#define flr(a, l, r) for(register int a = l; a < r; ++a)
#define frl(a, r, l) for(register int a = r; a > l; --a)
#define pb(a) push_back(a)
#endif // __defi

const signed N = 55;
__int128 w[N], f[N][N];
__int128 INF = (unsigned __int128) -1 >> 1;

void slove(int Case){ //printf("%d\n", Case );
    int in(n); flr(i, 1, n+1) in(w[i]);
    flr(len, 3, n+1) flr(l, 1, n-len+2){
        int r = l + len - 1;
        f[l][r] = INF;
        flr(k, l+1 , r){
            f[l][r] = min(f[l][r],  f[l][k] + f[k][r] + w[l]*w[k]*w[r]);
        }
    }
    //cout << f[1][n] << endl;
    write(f[1][n]);puts("");
}

#ifdef __test
#include "ctime"
#endif

signed main(){
        #ifdef __test
        #include "ctime"   
            freopen("in", "r", stdin);
            int t = clock();
        #endif
        int i = 0;
        #ifdef __loop
            int n; cin >> n; for(i = 0; i < n; ++i)
        #endif
            slove(i+1);
        #ifdef __test
            int s = clock();
            printf("all time is : %d ms\n", s - t);
            while(1);
        #endif
    }



活动打卡代码 AcWing 479. 加分二叉树

墨羽魂韶
18小时前
#include "iostream"
#include "vector"
using namespace std;

//#define __test
#define __defi
//#define __loop

#ifdef __defi
inline int read()
{
    int ans = 0, mark = 1;
    int t = getchar();
    while(t < '0' || t > '9'){
        if (t == '-') mark = -1;
        t = getchar();
    }
    while(t <= '9' && t >= '0'){
        ans = (ans << 3) + (ans << 1) + t - '0';
        t = getchar();
    }
    return ans * mark;
}


inline void write( int x ) {
    char F[ 200 ] ;
    int tmp = x > 0 ? x : -x ;
    if( x < 0 ) putchar( '-' ) ;
    int cnt = 0 ;
       while( tmp > 0 ) {
           F[ cnt ++ ] = tmp % 10 + '0' ;
           tmp /= 10 ;
       }
       while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}

#define in(a) a=read()
#define inn(a, b) in(a), in(b)
#define innn(a, b, c) in(a), in(b), in(c)
#define flr(a, l, r) for(register int a = l; a < r; ++a)
#define frl(a, r, l) for(register int a = r; a > l; --a)
#define pb(a) push_back(a)
#endif // __defi

const int N = 35;
int f[N][N], w[N], root[N][N];

void dfs(int l, int r){
    if(l > r) return;
    int k = root[l][r];
    cout << k+1 << " ";
    dfs(l, k-1); dfs(k+1 ,r);
}

void slove(int Case){ //printf("%d\n", Case );
    int in(n); flr(_,0,n) in(w[_]);
    flr(len, 1, n+1) flr(l, 0, n-len+1){
        int r = l + len - 1; flr(k, l, r+1){
            int ll = k == l ? 1 : f[l][k - 1];
            int rr = k == r ? 1 : f[k + 1][r];
            int sc = ll * rr + w[k];
            if (l == r) sc = w[k];
            if (f[l][r] < sc)
                f[l][r] = sc, root[l][r] = k;
        }
    }
    write(f[0][n-1]); puts(""); dfs(0, n-1); puts("");
}

#ifdef __test
#include "ctime"
#endif

signed main(){
        #ifdef __test
        #include "ctime"   
            freopen("in", "r", stdin);
            int t = clock();
        #endif
        int i = 0;
        #ifdef __loop
            int n; cin >> n; for(i = 0; i < n; ++i)
        #endif
            slove(i+1);
        #ifdef __test
            int s = clock();
            printf("all time is : %d ms\n", s - t);
            while(1);
        #endif
    }



活动打卡代码 AcWing 320. 能量项链

墨羽魂韶
19小时前
#include "iostream"
#include "vector"
using namespace std;

//#define __test
#define __defi
//#define __loop

#ifdef __defi
inline int read()
{
    int ans = 0, mark = 1;
    int t = getchar();
    while(t < '0' || t > '9'){
        if (t == '-') mark = -1;
        t = getchar();
    }
    while(t <= '9' && t >= '0'){
        ans = (ans << 3) + (ans << 1) + t - '0';
        t = getchar();
    }
    return ans * mark;
}


inline void write( int x ) {
    char F[ 200 ] ;
    int tmp = x > 0 ? x : -x ;
    if( x < 0 ) putchar( '-' ) ;
    int cnt = 0 ;
       while( tmp > 0 ) {
           F[ cnt ++ ] = tmp % 10 + '0' ;
           tmp /= 10 ;
       }
       while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}

#define in(a) a=read()
#define inn(a, b) in(a), in(b)
#define innn(a, b, c) in(a), in(b), in(c)
#define flr(a, l, r) for(register int a = l; a < r; ++a)
#define frl(a, r, l) for(register int a = r; a > l; --a)
#define pb(a) push_back(a)
#endif // __defi

const int N = 210;
int w[N], f[N][N];

void slove(int Case){ //printf("%d\n", Case );
    int in(n); flr(i, 0, n) w[i+n]=in(w[i]);
    flr(len, 1, n+1) flr(l, 0, 2*n+1-len){ 
        int r = l + len - 1; flr(k, l, r)
        f[l][r] = max(f[l][r], f[l][k] + f[k+1][r] + w[l]*w[r+1]*w[k+1]);
    }
    int res = -1; flr(i, 0, n)
        res = max(res, f[i][i+n-1]);
    write(res);puts("");
}

#ifdef __test
#include "ctime"
#endif

signed main(){
        #ifdef __test
            freopen("in", "r", stdin);
            int t = clock();
        #endif
        int i = 0;
        #ifdef __loop
            int n; cin >> n; for(i = 0; i < n; ++i)
        #endif
            slove(i+1);
        #ifdef __test
            int s = clock();
            printf("all time is : %d ms\n", s - t);
            while(1);
        #endif
    }



活动打卡代码 AcWing 1068. 环形石子合并

#include "iostream"
#include "vector"
#include "cstring"
using namespace std;

//#define __test
void slove(int Case){ //printf("%d\n", Case );
    // init
    int n; vector<int>  s(405), w(405); int f[205][205], g[205][205];
    cin >> n; for(int i = 1 ; i <= n; ++i){int t = 0;
    cin >> t; w[i+n] = w[i] = t;}
    for(int i = 1; i <= 2 * n; ++i) s[i] = s[i-1] + w[i];
    memset(f, 0x3f, sizeof f), memset(g, 0xcf, sizeof g);

    //dp
    for(int len = 1; len <= n; ++len){
        for(int l = 1; l + len - 1 <= n * 2; ++l){
            int r = l + len - 1;
            if (l == r) f[l][r] = g[l][r] = 0;
            else for (int k = l; k < r; k ++ ){
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
        }
    }

    // o
    int Max = 0xcfcfcfcf, Min = 0x3f3f3f3f;
    for(int i = 1; i < n + 1; i++){
        Min = min(Min, f[i][i+n-1]);
        Max = max(Max, g[i][i+n-1]);
    }
    cout << Min << endl << Max << endl;
}
#ifdef __test
    #include "ctime"
    signed main(){
        freopen("in", "r", stdin);
        int t = clock();
        int i = 0;
        //int n; cin >> n; for(i = 0; i < n; ++i)
            slove(i+1);
        int s = clock();
        printf("all time is : %d ms\n", s - t);
    }
#else
    signed main(){
    //int n; cin >> n; for(int i = 0; i < n; ++i)
        slove(1);
    return 0;
}
#endif



活动打卡代码 AcWing 292. 炮兵阵地

#include "iostream"
#include "vector"
using namespace std;

int N, M;
vector<int> state;
vector<int> cnt(1<<10);
int f[2][1<<10][1<<10];

inline bool check(int k){
    int t = k>>1 | k >> 2;
    if(t&k) return false;
    else return true;
}
inline int count(int k){
    int cnt = 0;
    while(++cnt&&k)
        k -= k & -k;
    return --cnt;
}

signed main(){
    cin >> N >> M;

    for(register int i = 0; i < 1<<M; ++i)
        if(check(i))
            state.push_back(i),\
            cnt[i] = count(i);

    for(register int i = 1, t = 0, tt = 0; i <= N; ++i, tt= t, t=0){
        for(register int j = 0; j < M; ++j){
            char c; cin >> c;
            if(c == 'H') t += 1<<j;
        }
        //cout << t << endl;
        for(int a : state) for(int b :state) for(int c :state){
            if(a & b || a & c || b & c) continue;
            if(t&b || tt&a) continue;
            f[i&1][a][b] = max(f[i&1][a][b], f[i-1&1][c][a] + cnt[b]);
        }
    }

    int ans = 0;
    for(int a : state) for(int b : state)
        ans = max(ans, f[N&1][a][b]);
    cout << ans << endl;

}



活动打卡代码 AcWing 327. 玉米田

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];

bool check(int state)
{
    for (int i = 0; i + 1 < m; i ++ )
        if ((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            int t;
            cin >> t;
            w[i] += !t * (1 << j);
        }

    for (int i = 0; i < 1 << m; i ++ )
        if (check(i))
            state.push_back(i);

    for (int i = 0; i < state.size(); i ++ )
        for (int j = 0; j < state.size(); j ++ )
        {
            int a = state[i], b = state[j];
            if (!(a & b))
                head[i].push_back(j);
        }

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
        for (int j = 0; j < state.size(); j ++ )
            if (!(state[j] & w[i]))
                for (int k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

    cout << f[n + 1][0] << endl;

    return 0;
}



活动打卡代码 AcWing 1064. 小国王

#include "iostream"
#include "vector"
using namespace std;

inline bool check(int i){
    int t = (i >> 1) | (i << 1);
    if(t & i)
        return false;
    else return true;
}

inline int count(int i){
    int cnt = 0;
    while(++cnt&&i){
        i -= i&-i;
    }
    return --cnt;
}
long long f[15][110][(int)1<<10];
vector<int> state, head[1<<10];
int cnt[(int)1<<10];
signed main(){
    int n, m; cin >> n >> m;

    // find all state
    for(register int i = 0; i < 1 << n; ++i){
        if(check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    // find all two-state
    for(register int i = 0; i < state.size(); ++i)
        for(register int j = 0; j < state.size(); ++j){
            long long int a = state[i], b = state[j];
            a = a|(a<<1)|(a>>1);
            if((a & b) == 0)
                head[i].push_back(j);
        }

    // DP
    f[0][0][0] = 1;
    for(register int i = 1; i <= n+1; ++i)
        for(register int j = 0; j <= m; ++j)
            for(register int k = 0; k < state.size(); ++k)
                    for(int a : head[k]){
                        int b = cnt[state[k]];
                        if(j >= b)
                            f[i][j][k] += f[i-1][j-b][a];
                    }

    cout << f[n+1][m][0] << endl;

}




链接
遇到的问题:
+ 当 n 大于 5 的时候会出现 sg 错误

#include "iostream"
#include "vector"
using namespace std;

inline bool check(int i){
    int t = (i >> 1) | (i << 1);
    if(t & i)
        return false;
    else 
        return true;
}

inline int count(int i){
    int cnt = 0;
    while(++cnt&&i){
        i -= i&-i;
    }
    return --cnt;
}
// n:10 k:n^2 state:1<<10
long long f[15][110][(int)1<<10];
vector<int> state, head[15];
int cnt[(int)1<<10];

signed main(){
    int n, m; cin >> n >> m;

    // find all state
    for(register int i = 0; i < 1 << n; ++i){
        if(check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    // find all two-state
    for(register int i = 0; i < state.size(); ++i)
        for(register int j = 0; j < state.size(); ++j){
            long long int a = state[i], b = state[j];
            a = a|(a<<1)|(a>>1);
            if((a & b) == 0)
                head[i].push_back(j);
        }

    // DP
    f[0][0][0] = 1;
    for(register int i = 1; i <= n+1; ++i)
        for(register int j = 0; j <= m; ++j)
            for(register int k = 0; k < state.size(); ++k)
                    for(int a : head[k]){
                        int b = cnt[state[k]];
                        if(j >= b)
                            f[i][j][k] += f[i-1][j-b][a];
                    }

    cout << f[n+1][m][0] << endl;

}


活动打卡代码 AcWing 1058. 股票买卖 V

#include<bits/stdc++.h>
using namespace std;
#define int long long 

signed main(){
    int n; int INF = (unsigned) -1 >> 1;
    int a = 0, b = -INF-1, c = -INF-1, k = 0; 
    for(cin >> n; ~n; n--){
        int ta = a;
        a = b+k;
        b = max(b, c-k);
        c = max(c, ta);
        //cout << k << " " << a << " " << b << " " << c << endl;
        cin >> k;
    }
    cout << max(a, c) << endl;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline int read(){
int ans=0,mark=1;char t=getchar();
while(t<'0'||t>'9'){if(t=='-')mark=-1;t = getchar();}
while(t<='9'&&t>='0'){ans=(ans<<3)+(ans<<1)+t-'0';t=getchar();}
return ans * mark;}
#define in(x) (x)=read()
#define inn(x, y) in(x),in(y)
#define innn(x, y, z) inn(x, y),in(z)
#define flr(i, l, r) for(int i = l; i < r; ++i)
#define frl(i, r, l) for(int i = r; i > l; --i)
#define V vector<int>
#define pb(x) push_back(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int A[3][105];

signed main(){
    int inn(n, m); memset(A, 0xcf, sizeof A); A[0][0] = 0;
    flr(_, 0, n){
        int in(k);
        frl(i, m, 0){
            A[0][i] = max(A[0][i], A[1][i]+k);
            A[1][i] = max(A[1][i], A[0][i-1]-k);
        }
        //cout << k << endl;
        //flr(i, 0, m+1) cout << A[0][i] << " "; cout << endl;
        //flr(i, 0, m+1) cout << A[1][i] << " "; cout << endl;
    }int ans = 0;flr(i, 0, m+1)
        ans = max(ans, max(A[0][i], A[1][i]));  
    cout << ans << endl;
}