头像

呼和


访客:6330

离线:3天前


活动打卡代码 AcWing 1072. 树的最长路径

呼和
12天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int head[N],w[N],ne[N],to[N],id = 0;
int ans = 0;
void add(int a,int b , int c)
{
    ++id;
    w[id] = c;
    ne[id] = head[a];
    to[id] = b;
    head[a] = id;
}
int dfs(int u,int fa)
{   
    int d1 = 0,d2 = 0,d;
    for(int i = head[u] ; i ; i = ne[i])
    {
        int e = to[i];
        if(e == fa)
            continue;
        d = dfs(e, u) + w[i];
        if(d > d1)
        {
            d2 = d1;
            d1 = d;
        }
        else if(d > d2)
        {
            d2 = d;
        }
    }
    if(ans < d1 + d2)
        ans = d1 + d2;
    return d1;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i < n ;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1, 0);
    cout << ans << endl;
}



呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 110;
const int m = 40;
ll a[N];
ll dp[N][N][m];
void cheng(ll x[] , ll y)
{
    ll p = 0 ;
    for(ll i = 0 ; i < m - 1 ; i++)
    {
        x[i] *= y;
        x[i] += p;
        p = x[i]/10;
        x[i]%=10;
    }
}
void add(ll x[] , ll y[])
{
    for(int i = 0 ; i < m - 1 ; i++ )
    {
        x[i] += y[i];
        x[i+1] += x[i]/10;
        x[i] %= 10;
    }
}
bool cmp(ll x[] , ll y[])
{
    for(ll i = m-1 ; i >= 0 ; i--)
    {
        if(x[i] > y[i])
            return false;
        else if(x[i] < y[i])
            return true; 
    }
}
void print(ll x[])
{
    int len = m-1;
    while(x[len] == 0 && len >= 0)
        len--;
    for(int i = len ; i >= 0 ; i--)
        cout << x[i];
    cout << endl;
}
int main()
{
    int n ;
    cin >> n;
    for(int i = 1; i <= n ; i++)
    {
        cin >> a[i];
    }
    for(int k = 3 ; k <= n ; k++)
    {
        for(int l = 1 ; l <= n - k + 1; l++)
        {
            int r = l + k - 1;
            dp[l][r][m-1] = 1;
            for(int i = l+1 ; i < r ; i++)
            {
                ll t[m];
                memset(t, 0 ,sizeof(t));
                t[0] = 1;
                cheng(t, a[l]);
                cheng(t, a[r]);
                cheng(t, a[i]);
                add( t, dp[l][i]);
                add( t, dp[i][r]);
                if(cmp(t , dp[l][r]))
                    memcpy(dp[l][r] , t , sizeof(dp[l][r]));
            }
        }
    }
    print(dp[1][n]);
}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 110;
int dp[N][N];
int st[N][N];
int a[N];
void dfs(int l , int r )
{
    if(l > r)
        return ;
    int x = st[l][r];
    cout << x << " ";
    dfs(l , x - 1);
    dfs(x + 1 , r);
}
int main()
{
    int n;
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];

    for(int k = 1 ; k <= n ; k++)
    {
        for(int l = 1; l <= n - k + 1; l++)
        {
            int r = l + k - 1;
            if(l == r)
            {
                st[l][r] = l;
                dp[l][r] = a[l];
            }
            else 
            {
                for(int i = l ; i <= r ; i++)
                {
                    int ll,rr;
                    ll = (i == l) ? 1 : dp[l][i-1];
                    rr = (i == r) ? 1 : dp[i+1][r];
                    int data = ll * rr + a[i];
                    if(data > dp[l][r])
                    {
                        st[l][r] = i;
                        dp[l][r] = data;
                    }
                }               
            }
        }
    }
    cout << dp[1][n] << endl;

    dfs(1 , n);
    cout << endl;
}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 310;
int a[N];
LL dp[N][N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ;i++)
    {
        cin >> a[i];
        a[i + n ] = a[i];
    }

    for(int k = 2 ; k <= n ; k++)
        for(int l = 1 ; l <= 2*n - k + 1 ;  l++)
        {
            int r = l + k - 1;
            for(int i = l ; i < r ; i++)
            {
                dp[l][r] = max(dp[l][r] , dp[l][i] + dp[i+1][r] + a[l] * a[i+1] * a[r+1]);
            }
        }

    LL ans = 0;
    for(int i = 1 ; i <= n ; i++)
        ans = max(ans , dp[i][i+n-1]);  // 从i开始往后的n个当中的最大值
    cout << ans << endl;

}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 410;
int f[N][N];
int g[N][N];
int a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1 ;i <= n ; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }
    memset(f , -0x3f3f3f3f, sizeof(f));
    memset(g , 0x3f3f3f3f, sizeof(g));
    for(int i = 1 ;i <= 2 * n ; i++)
    {
        a[i] += a[i-1];
        f[i][i] = g[i][i] = 0;
    }
    for(int k = 2 ; k <= n ; k++)
        for(int l = 1 ; l + k - 1 <= 2 * n ; l++ )
        {
            int r = l + k - 1;
            int ans = a[r] - a[l-1];
            for(int j = l ; j < r ; j++)
            {
                f[l][r] = max(f[l][r] , f[l][j] + f[j+1][r] + ans);
                g[l][r] = min(g[l][r] , g[l][j] + g[j+1][r] + ans);

            }
        }
    int maxx , minn;
    maxx =0 ;
    minn = 0x3f3f3f3f;
    for(int i = 1 ; i<= n ;i ++)
    {
        minn = min(minn , g[i][i+n-1]);
        maxx = max(maxx , f[i][i+n-1]);
    }
    cout << minn << endl << maxx << endl;
}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1 << 13;
const int W = 15;
const int mod = 100000000;

LL dp[W][N];
int st[W];

int main()
{
    int n , m , a;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> a;
            st[i] =st[i] * 2 + a;
        }
    }
    memset(dp , 0 , sizeof(dp));
    dp[0][0] = 1;
    int t = 1 << m;
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 0 ; j < t ; j++)
        {
            if(j & (j << 1) || j & (j >> 1))
                continue;
            if( (st[i] & j) != j)
                continue;
            for(int k = 0 ; k < t ; k++)
            {
                if(j & k)
                    continue ;
                dp[i][j] += dp[i-1][k];
                dp[i][j] %= mod;
            }
        }
    }
    for(int i =  0 ; i <= n ; i++)
    {
        for(int j = 0 ; j < t; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    LL ans = 0;
    for(int i = 0 ; i < t ; i++)
        ans = (ans + dp[n][i]) % mod;
    cout << ans << endl;
}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1 << 13;
const int W = 15;
const int mod = 100000000;

LL dp[W][N];
int st[W];

int main()
{
    int n , m , a;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> a;
            st[i] =st[i] * 2 + a;
        }
    }
    memset(dp , 0 , sizeof(dp));
    dp[0][0] = 1;
    int t = 1 << m;
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 0 ; j < t ; j++)
        {
            if(j & (j << 1) || j & (j >> 1))
                continue;
            if( (st[i] & j) != j)
                continue;
            for(int k = 0 ; k < t ; k++)
            {
                if(j & k)
                    continue ;
                dp[i][j] += dp[i-1][k];
                dp[i][j] %= mod;
            }
        }
    }
    for(int i =  0 ; i <= n ; i++)
    {
        for(int j = 0 ; j < t; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    LL ans = 0;
    for(int i = 0 ; i < t ; i++)
        ans = (ans + dp[n][i]) % mod;
    cout << ans << endl;
}


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

呼和
13天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1<<11;
LL f[11][N][110]; // 这里需要LL
int st[N];
int flag[N];
int len = 0;
void get(int x , int i )
{
    while(x)
    {
        x -= (x & - x);
        st[i]++;
    }
}
void init(int n)
{
    memset(flag , true , sizeof(flag));
    for(int i = 0 ; i < (1 << n) ; i++)
    {
        if(i & (i << 1) || i & (i >> 1))
            flag[i] = false;
        else 
            get(i , i);
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    init(n);
    f[0][0][0] = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < (1 << n) ; j++)
        {
            if(flag[j])
            for(int k = 0 ; k < (1 << n) ; k++)
            {
                if( (j&k) || !flag[k | j])
                    continue;

                for(int l = 0 ; l <= m - st[j] ; l++)
                {
                    f[i][j][ st[j] + l ] += f[i-1][k][l];
                }
            }
        }
    }
    LL sum = 0;
    for(int i = 0 ; i < (1 << n) ; i++)
        sum += f[n][i][m];
    cout << sum << endl;
}


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

呼和
14天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int dp[N][110][2];
int a[N];
int main()
{
    int n , k;
    scanf("%d%d",&n,&k);
    memset(dp,-0x3f3f, sizeof(dp));
    dp[0][0][0] = 0;

    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&a[i]);
        dp[i][0][0] = 0;
    }




    for(int i = 1; i <= n ;i++)
    {
        for(int j = 1 ; j <= k ; j++)
        {
            dp[i][j][1] = max(dp[i-1][j][1] , dp[i-1][j-1][0] - a[i]);
            dp[i][j][0] = max(dp[i-1][j][0] , dp[i-1][j][1] + a[i]);
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= k ; i++)
        ans = max(ans , dp[n][i][0]);
    printf("%d",ans);

}


活动打卡代码 AcWing 734. 能量石

呼和
14天前
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
struct Node 
{
    int s,e,l;
    bool operator < (const Node &x) const{
        return s * x.l < x.s * l;
    }
}p[110];
int dp[10010];
int main()
{
    int T;
    cin >>T;
    for(int l = 1 ; l <= T; l++)
    {
        int n;
        cin >> n;
        int sum =0;
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n ; i++)
        {
            cin >> p[i].s >> p[i].e >> p[i].l;
            sum += p[i].s;
        }
        sort(p+1 , p+1+n);

        for(int i = 1 ; i <= n ; i++)
        {
            int s = p[i].s;
            int e = p[i].e;
            int l = p[i].l;
            for(int j = sum; j >= s ; j--)
            {
                dp[j] = max(dp[j] , dp[j - s ] + e - l  * (j - s) );
            }
        }
        int ans = 0;
        for(int i = 0 ; i <= sum ; i++)
            ans = max(ans , dp[i]);

        printf("Case #%d: %d\n",l , ans);
    }
}