头像

dfbdberberb




离线:7小时前


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

#include<iostream>
#include<algorithm>

using namespace std;
const int N =14,M=1<<14;
int n,m;
vector<int> vaild[N];
int a[N];
int f[N][M];

bool check(int id,int state)
{
    for(int i=0;i<m;i++)
    {
        if(!(a[id] >>i&1)&&state>>i&1) return false;  //检测是否是坏田
        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++)
            {
                a[i]<<=1;
                int t;
                cin>>t;
                a[i]+=t;
            }




    for(int i=1;i<=n;i++)
        for(int j=0;j<1<<m;j++)
        {
            if(check(i,j))
            vaild[i].push_back(j);
        }

        for(auto i:vaild[1])
            f[1][i] = 1;

    for(int i=2;i<=n;i++)
        for(auto j:vaild[i])
            for(auto k:vaild[i-1] )
            {
                if((j&k)==0)
                f[i][j] +=f[i-1][k];
            }

        int res =0;
    for(auto i:f[n])
    res=(res+i)%100000000;
    cout<<res<<endl;


    return 0;
}




#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1003;
int w[N],a[N],f[N][N],g[N][N];
int n,m,k;


int main()
{
    cin>>n>>m>>k;

    for(int i=1;i<=k;i++)
        cin>>w[i]>>a[i];

      for(int i=1;i<=k;i++)
         for(int j=n;j>=w[i];j--)
             for(int l=m;l>=a[i];l--)
             {
                 if(f[j][l]<f[j-w[i]][l-a[i]]+1)
                 {
                    f[j][l] = f[j-w[i]][l-a[i]]+1;
                    // g[j][l] = g[j-w[i]][l-a[i]]+ a[i];
                 }
             }

    int i=m-1;
    while(i>0&&f[n][m-1]==f[n][i-1]) i--;

    cout<<f[n][m-1]<<' '<<m- i;

    return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

#include<iostream>
#include<algorithm>

using namespace std;
int n, v;
int dp[33][200004];
int a[33];
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];


    for(int i=1;i<=n;i++)
        for(int j=0;j<=v;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=a[i])
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]+a[i] );
        }
    cout<<v -dp[n][v];





    return 0;
}


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5+10;

int a[N];

int n;
int f[N][3];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];


    f[1][1]=-a[1];


    for(int i=2;i<=n;i++)
        {
          f[i][0] = max(f[i-1][0] , f[i-1][1]+a[i]);

          if(i>2)
          f[i][1] = max(f[i-1][1],f[i-2][0]-a[i]);
          else
          f[i][1] = max(f[i-1][1],-a[i]);
        }

    cout<<max(f[n][0],f[n][1]);


    return 0;
}


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

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

using namespace std;
const int N= 1e5+10;
int n,k;
int a[N];
int f[N][103][2];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    memset(f,-0x3f ,sizeof f);
    for(int i=0;i<=n;i++)
        f[i][0][0]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
        {
            f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+a[i]);
            f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-a[i]);
        }
    int res =0;
    for(int i=0;i<=k;i++)
        res = max(res,f[n][i][0]);

    cout<<res;

    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

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


using namespace std;
const int N=100003;
int n,k;
int a[N],dp[N][2];


int main()
{
    cin>>n;
    while(n--)
    {
        // for(int i=0;i<)
        // memset(dp,0,sizeof dp);
        // memset(a,0,sizeof a);
        cin>>k;
        for(int i=0;i<k;i++)
            cin>>a[i];
        dp[0][0]=0;
        dp[0][1]=a[0];
        for(int i=1; i<k; i++)
            {
                dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
                dp[i][1] = dp[i-1][0]+a[i];

            }

        cout<<max(dp[k-1][1],dp[k-1][0])<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 423. 采药

#include<iostream>
#include<algorithm>

using namespace std;
const int N  = 1003;
int a[N],w[N],dp[N][N];
int t,n;

int main()
{
    cin>>t>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>w[i];
    }

    for(int i=1;i<=n;i++)
        for(int j=0;j<=t;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=a[i])
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]]+w[i] );
        }
        cout<<dp[n][t];



    return 0;
}



#include<iostream>
#include<algorithm>

using namespace std;
const int N=3004;
int a[N],b[N],f[N][N];
int n;

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    for (int i=1;i<=n;i++)
    cin>>b[i];

    for (int i=1;i<=n;i++)
      {
        int maxv =1;
        for (int j=1;j<=n;j++)
            {
                f[i][j]=f[i-1][j];
                if(a[i]==b[j])  f[i][j]=max(f[i][j],maxv);
                if(a[i]>b[j] )   maxv=max(maxv ,f[i-1][j]+1);

            }

         }   
            int res=0;
    for (int i=0;i<=n;i++)
    // cout<<i<<endl;
         res = max(res,f[n][i]);
    cout<<res;



    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1003;
int n;
int a[N];
int dp[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i],dp[i]=a[i];

    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[j]<a[i])
        dp[i]=max(dp[i],dp[j]+a[i]);


    int res = 0;    
    for(int i=0;i<n;i++)
    {
        // cout<<dp[i]<<endl;
        res = max(res , dp[i]);
    }

    cout<<res<<endl;


    return 0 ;
}


活动打卡代码 AcWing 1012. 友好城市

#include<iostream>
#include<algorithm>

using namespace std;
const int N =5005;
int dp[N];
pair<int ,int > a[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int c,b;
        cin>>c>>b;
        a[i]={c,b};
    }
    sort(a,a+n);
    // for(int i=0;i<n;i++)
    // cout<<a[i].first<<' '<<a[i].second<<endl;
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        if(a[i].second>a[j].second)
            dp[i] = max(dp[i],dp[j]+1);
            int  res =0;
    for(int i=0;i<n;i++)
    res = max(res, dp[i]+1);

    cout<<res <<endl;

    return 0;
}