头像

vlily




离线:7天前


最近来访(45)
用户头像
庸人_9
用户头像
sumlist
用户头像
最後の祈りを
用户头像
猪啊猪
用户头像
GortoN
用户头像
WilliamWang
用户头像
jasonho
用户头像
kroyosh
用户头像
匡匡y
用户头像
二十九画生
用户头像
小憨憨
用户头像
slytherin
用户头像
zombotany
用户头像
thezhu
用户头像
Schucking_Sattin
用户头像
jerry2008
用户头像
SillyBoy
用户头像
Wsnemo
用户头像
贪心的小马
用户头像
1..

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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,a[5000],dp[5000][5000],mx;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
    for(int len=3;len<=n+1;len++){
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            for(int k=l+1;k<r;k++)dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[r]*a[k]);
        }
    }
    for(int i=1;i<=n;i++)mx=max(mx,dp[i][i+n]);
    cout<<mx<<endl;
    return 0;
}


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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,a[500],dpmax[500][500],dpmin[500][500],sum[500],mx,mi=2e9;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
    for(int i=1;i<=2*n;i++)sum[i]=sum[i-1]+a[i];
    memset(dpmax,-0x3f,sizeof dpmax);
    memset(dpmin,0x3f,sizeof dpmin);
    for(int len=1;len<=n;len++){
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            if(len==1)dpmax[l][r]=dpmin[l][r]=0;
            else{
                for(int k=l;k<r;k++){
                    dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r]+sum[r]-sum[l-1]);
                    dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r]+sum[r]-sum[l-1]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        mx=max(mx,dpmax[i][i+n-1]);
        mi=min(mi,dpmin[i][i+n-1]);
    }
    cout<<mi<<endl<<mx<<endl;
    return 0;
}


活动打卡代码 AcWing 524. 愤怒的小鸟

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
pair<double,double>q[20];
int t,n,m,dp[300030],path[20][20];
int cmp(double a,double b){
    if(fabs(a-b)<eps)return 0;
    if(a<b)return -1;
    return 1;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        memset(path,0,sizeof path);
        memset(dp,0x3f,sizeof dp);
        dp[0]=0;
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>q[i].first>>q[i].second;
        for(int i=0;i<n;i++){
            path[i][i]=1<<i;
            for(int j=0;j<n;j++){
                double x1=q[i].first,y1=q[i].second,x2=q[j].first,y2=q[j].second;
                if(!cmp(x1,x2))continue;
                double a=(y1/x1-y2/x2)/(x1-x2),b=y1/x1-a*x1;
                if(cmp(a,0)>=0)continue;
                int state=0;
                for(int k=0;k<n;k++)if(!cmp(a*q[k].first*q[k].first+b*q[k].first,q[k].second))state+=1<<k;
                path[i][j]=state;
            }
        }
        for(int i=0;i+1<1<<n;i++){
            int x=0;
            for(int j=0;j<n;j++){
                if(!(i>>j&1)){
                    x=j;
                    break;
                }
            }
            for(int j=0;j<n;j++)dp[i|path[x][j]]=min(dp[i|path[x][j]],dp[i]+1);
        }
        cout<<dp[(1<<n)-1]<<endl;
    }
    return 0;
}


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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,m,g[1010],dp[2][2000][2000],cnt[2000];
vector<int>state;
bool check(int state){
    for(int i=0;i<m;i++)if((state>>i&1)&&((state>>i+1&1)||(state>>i+2&1)))return 0;
    return 1;
}
int count(int state){
    int res=0;
    for(int i=0;i<m;i++)if(state>>i&1)res++;
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            g[i]+=(c=='H')<<j;
        }
    }
    for(int i=0;i<1<<m;i++){
        if(check(i)) state.push_back(i);
        cnt[i]=count(i);
    }
    for(int i=1;i<=n+2;i++){
        for(int j=0;j<state.size();j++){
            for(int k=0;k<state.size();k++){
                for(int u=0;u<state.size();u++){
                    int a=state[j],b=state[k],c=state[u];
                    if((a&b)|(b&c)|(a&c))continue;
                    if(g[i-1]&a|g[i]&b)continue;
                    dp[i&1][j][k]=max(dp[i&1][j][k],dp[i-1&1][u][j]+cnt[b]);
                }
            }
        }
    }
    cout<<dp[n+2&1][0][0]<<endl;
    return 0;
}


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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
const int mod=1e8;
int n,m,x,w[20],dp[20][5000];
vector<int>state,head[5000];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            cin>>x;
            w[i]+=!x*(1<<j);
        }
    }
    for(int i=0;i<1<<m;i++)if((i&i>>1)==0)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)==0)head[i].push_back(j);
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=n+1;i++)for(int j=0;j<state.size();j++)if((state[j]&w[i])==0)for(auto k:head[j])dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
    cout<<dp[n+1][0]<<endl;
    return 0;
}


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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[1100];
long long dp[20][110][1100];
vector<int>head[1100],state;
bool check(int x){
    for(int i=0;i<n;i++)if((x>>i&1)&&(x>>i+1&1))return 0;
    return 1;
}
int count(int x){
    int res=0;
    for(int i=0;i<n;i++)if(x>>i&1)res++;
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<1<<n;i++){
        if(check(i)){
            state.push_back(i);
            cnt[i]=count(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)==0&&check(a|b))head[i].push_back(j);
        }
    }
    dp[0][0][0]=1;
    for(int i=1;i<=n+1;i++){
        for(int j=0;j<=m;j++){
            for(int a=0;a<state.size();a++){
                for(auto b:head[a]){
                    int c=cnt[state[a]];
                    if(j>=c) dp[i][j][a]+=dp[i-1][j-c][b];
                }
            }
        }
    }
    cout<<dp[n+1][m][0]<<endl;
    return 0;
}


活动打卡代码 AcWing 1052. 设计密码

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
const int 60=55,mod=1e9+7;
int n,ne[60],dp[60][60],res;
char t[60];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>t+1;
    int m=strlen(t+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&t[i]!=t[j+1])j=ne[j];
        if(t[i]==t[j+1])j++;
        ne[i]=j;
    }
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(char k='a';k<='z';k++){
                int u=j;
                while(u&&k!=t[u+1])u=ne[u];
                if(k==t[u+1])u++;
                if(u<m)dp[i+1][u]=(dp[i+1][u]+dp[i][j])%mod;
            }
        }
    }
    for(int i=0;i<m;i++)res=(res+dp[n][i])%mod;
    cout<<res<<endl;
    return 0;
}


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

vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],dp[100010][3];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    dp[0][2]=0;
    dp[0][1]=dp[0][0]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][2]-a[i]);
        dp[i][1]=dp[i-1][0]+a[i];
        dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
    }
    cout<<max(dp[n][1],dp[n][2])<<endl;
    return 0;
}


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

vlily
2个月前

````

include[HTML_REMOVED]

using namespace std;
int dp[110000][110][2],n,k,res,a[110000];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i)cin>>a[i];
memset(dp,-0x3f,sizeof dp);
for(int i=0;i<=n;i
)dp[i][0][0]=0;
for(int i=1;i<=n;i)for(int j=1;j<=k;j)dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+a[i]),dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-a[i]);
for(int i=0;i<=k;i++)res=max(res,dp[n][i][0]);
cout<<res<<endl;
return 0;
}
```




vlily
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,p,q,dp[33000];
pair<int,int>zhu[80];
vector<pair<int,int>>fu[80];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>v>>p>>q;
        p*=v;
        if(!q)zhu[i]={v,p};
        else fu[q].push_back({v,p});
    }
    for(int i=1;i<=n;i++){
        for(int u=m;u>=0;u--){
            for(int j=0;j<1<<fu[i].size();j++){
                v=zhu[i].first,w=zhu[i].second;
                for(int k=0;k<fu[i].size();k++){
                    if(j>>k&1){
                        v+=fu[i][k].first;
                        w+=fu[i][k].second;
                    }
                }
                if(u>=v)dp[u]=max(dp[u],dp[u-v]+w);
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}