头像

雅俗doctor




离线:8小时前


最近来访(3)
用户头像
时间路人_4
用户头像
Approc
用户头像
violet_garden

活动打卡代码 AcWing 1252. 搭配购买

#include<bits/stdc++.h>
using namespace std;
const int M=10010;
int p[M],back_w[M],val[M],dp[2][M];
int n,m,w;
int find(int x){
    return p[x]=p[x]!=x?find(p[x]):p[x];
}
int main(){
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++) p[i]=i;
    vector<pair<int,int>> vr;
    int bn=n;
    while(bn--){
        int c,d;
        cin>>c>>d;
        vr.push_back({c,d});
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        p[find(a)]=find(b);
    }
    for(int i=1;i<=n;i++){
        back_w[find(i)]+=vr[i-1].first;
        val[find(i)]+=vr[i-1].second;
    }
    int now=0,old=1;
    for(int i=1;i<=n;i++){
        swap(now,old);
        for(int j=1;j<=w;j++){
            dp[now][j]=dp[old][j];
            if(j>=back_w[i])
                dp[now][j]=max(dp[old][j],dp[old][j-back_w[i]]+val[i]);
        }
    }
    cout<<dp[now][w];
}


活动打卡代码 AcWing 1250. 格子游戏

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(flase);cin.tie(0);
const int M=40010;
int p[M];
int n,m;
int find(int x){
    return p[x]=p[x]!=x?find(p[x]):p[x];
}
int get(int x,int y){
    return (x-1)*n+y-1;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n*n;i++) p[i]=i;
    int ans=0;
    for(int i=0;i<m;i++){
        int x,y;
        char c;
        cin>>x>>y>>c;
        int b,e;
        b=get(x,y);
        if(c=='D') e=get(x+1,y);
        else e=get(x,y+1);
        int pb=find(b),pe=find(e);
        if(pb==pe){
            ans=i+1;
            break;
        }
        p[pb]=pe;
    }
    if(!ans) cout<<"draw"<<endl;
    else cout<<ans<<endl;
}



当你没有数学知识也不懂一维优化时


当你没有数学知识也不懂一维优化时

BASE

1.看数据大小,能确定包子能拿来跑程序,能拿来凑的就只有10000个
2.综合完全背包问题,dp(i,j)表示为当前有i个笼子,能否凑出第j个数,写出完全背包的状态转移方程,最后统计当前有n个笼子时,从1-10000中凑不到的数目。


如何确定是否为INF无穷个数目?

由BASE知,跑程序的有10000个,所以ans肯定比10000小
其次,读题,假设对于蒸笼容量为4,5时,凑不到的数目有1,2,3,6,7,11
那么1,2,3是因为小于4所以凑不到得的,由此可见总数为6的答案数列是由一个前紧凑后稀疏的数列构成的

那么对于10000个拿来拼凑的数据,凑不到的数目构成的数列也是前紧凑后稀疏的,所以对于足够大的测试数据,有限个凑不到的数目是小于总测试数据的一半的
所以假设题意正确,那么ans>=10000/2即可判断为无穷


不会一维如何优化呢

那就二维滚动数组呗,初始为dp[2][10005],让old=0,now=1,每次old和now之间滚动计算状态,即用now表示i,old表示i-1,交换old和now来实现存储和计算

bool dp[2][10010];
int old=1,now=0;
for(int i=1;i<=n;i++){
    swap(old,now);
    for(int j=0;j<=10000;j++)
        dp[now][j]=dp[old][j]....;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const string ER="INF";
const int M=110;
int a[M];
bool dp[2][10010];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0][0]=1;
    int old=1,now=0;
    for(int i=1;i<=n;i++){
        swap(old,now);
        for(int j=0;j<=10000;j++)
            dp[now][j]=dp[old][j]||(j>=a[i]?dp[now][j-a[i]]:0);
    }
    int ans=0;
    for(int j=1;j<=10000;j++){
        if(ans>=5000){
            cout<<ER<<endl;
            return 0;
        }
        if(!dp[now][j]) ans++;
    }
    cout<<ans<<endl;
}



活动打卡代码 AcWing 1214. 波动数列

#include<bits/stdc++.h>
using namespace std;
const int MOD=100000007;
int dp[1010][1010];
int get_mod(int a,int b){
    return (a%b+b)%b;
}
int main(){
    int n,s,a,b;
    cin>>n>>s>>a>>b;
    dp[0][0]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=(dp[i-1][get_mod(j-(n-i)*a,n)]+dp[i-1][get_mod(j+(n-i)*b,n)])%MOD;
    cout<<dp[n-1][get_mod(s,n)]<<endl;
}


活动打卡代码 AcWing 1212. 地宫取宝

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=60;
int a[M][M],dp[M][M][14][14];
int MOD=1000000007;
int main(){
    int n,m,cv;
    cin>>n>>m>>cv;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]++;
        }
    }
    dp[1][1][1][a[1][1]]=1;
    dp[1][1][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=12;k++){
                for(int w=0;w<=13;w++){
                    int &val=dp[i][j][k][w];
                    val=(val+dp[i-1][j][k][w])%MOD;
                    val=(val+dp[i][j-1][k][w])%MOD;
                    if(w==a[i][j]&&k>0)
                        for(int c=0;c<w;c++){
                            val=(val+dp[i-1][j][k-1][c])%MOD;
                            val=(val+dp[i][j-1][k-1][c])%MOD;
                        }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=13;i++)
        ans=(ans+dp[n][m][cv][i])%MOD;
    cout<<ans<<endl;
}



#include<bits/stdc++.h>
using namespace std;
const int M=1010;
#define LL long long
LL a[M],dp[M];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    LL res=0;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
        res=max(res,dp[i]);
    }
    cout<<res;
}


活动打卡代码 AcWing 1015. 摘花生

#include<bits/stdc++.h>
using namespace std;
const int M=110;
int dp[M][M],bag[M][M];
int main(){
    int t,r,c;
    cin>>t;
    while(t--){
        memset(bag,0,sizeof bag);
        memset(dp,0,sizeof dp);
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>bag[i][j];
            }
        }
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                dp[i][j]=max(dp[i-1][j]+bag[i][j],dp[i][j-1]+bag[i][j]);
            }
        }
        cout<<dp[r][c]<<endl;
    }
}


活动打卡代码 AcWing 2. 01背包问题

#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int dp[M];
int v[M],w[M];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[m];
}


活动打卡代码 AcWing 1216. 饮料换购

#include<bits/stdc++.h>
using namespace std;
const int M=1e5;
int main(){
    int n;
    cin>>n;
    int ans=n;
    while(n>=3){
        n-=2;
        ans+=1;
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 1205. 买不到的数目

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
bool dp[M];
int main(){
    int n,m;
    cin>>n>>m;
    int mini=min(n,m);
    int maxi=max(n,m);
    dp[mini]=true;
    dp[maxi]=true;
    int ans=-1;
    for(int i=mini;i<=m*n;i++){
        if(dp[i-mini])
            dp[i]=true;
        else if(i>=maxi&&dp[i-maxi])
            dp[i]=true;
        if(!dp[i]) ans=max(ans,i);
    }
    cout<<ans<<endl;
}