头像

initialize

Do or do not.There is no try!




离线:7小时前



#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N],a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    cout<<res;
    return 0;
}




正序版

#include<iostream>
using namespace std;
const int N=510;
int a[N][N];
int f[N][N];
int main()
{
    int n,maxInteger;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++) 
            f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    maxInteger=f[n][1];
    for(int i=2;i<=n;i++)
    {
        if(f[n][i]>maxInteger) maxInteger=f[n][i];
    }
    cout<<maxInteger;

}

倒叙版

#include<iostream>
using namespace std;
const int N=510;
int a[N][N];
int f[N][N];
int main()
{
    int n,maxInteger;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++) 
            f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=n;i>=1;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);

    cout<<f[1][1];

}


活动打卡代码 AcWing 898. 数字三角形

正序版

#include<iostream>
using namespace std;
const int N=510;
int a[N][N];
int f[N][N];
int main()
{
    int n,maxInteger;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++) 
            f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    maxInteger=f[n][1];
    for(int i=2;i<=n;i++)
    {
        if(f[n][i]>maxInteger) maxInteger=f[n][i];
    }
    cout<<maxInteger;

}

倒叙版

#include<iostream>
using namespace std;
const int N=510;
int a[N][N];
int f[N][N];
int main()
{
    int n,maxInteger;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) 
            cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++) 
            f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=n;i>=1;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);

    cout<<f[1][1];

}


活动打卡代码 AcWing 9. 分组背包问题

#include<iostream>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=0;j<s[i];j++) cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=0;j--)
        {
            for(int k=0;k<s[i];k++)
            {
                if(v[i][k]<=j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout<<f[V];
}


活动打卡代码 LeetCode 9. 回文数

class Solution {
public:
    int isPalindrome(int x) {
        long res=0;
        int tmp=x;
        if(x<0) return false;
        while(tmp)
        {
            res=res*10+(tmp%10);
            tmp/=10;
        }
        if(res==x) return true;
        return false;
    }
};



class Solution {
public:
    int myAtoi(string s) {
        long long res=0;
        char symbol='+';
        bool connection=false;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]>='0' && s[i]<='9')
            {
                if(i-1>=0 && s[i-1]=='-') symbol='-';
                res=res*10+(s[i]-'0');
                if((symbol=='-'?-res:res)>INT_MAX) return INT_MAX;
                else if((symbol=='-'?-res:res)<INT_MIN) return INT_MIN;
                connection=true;
            }
            else {
                if(connection==true) break;
                if(s[i]!=' ')
                {
                    if((s[i]=='+' || s[i]=='-') && i+1<s.size() && s[i+1]>='0' && s[i+1]<='9') ;
                    else break;
                }

            }
        }
        if(symbol=='-') res=-res;
        return res;
    }
};


活动打卡代码 LeetCode 7. 整数反转

class Solution {
public:
    int reverse(int x) {
     int res=0;
     while(x)
      {
          if(x>0 && res>(INT_MAX-x%10)/10) return 0;
          if(x<0 && res<(INT_MIN-x%10)/10) return 0;
          res=res*10+x%10;
          x/=10;
      }
      return res;
    }
};


活动打卡代码 LeetCode 6. Z 字形变换

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if(numRows==1) return s;
        for(int i=0;i<numRows;i++)
        {
            if(i==0 || i==numRows-1) 
            {
                for(int j = i ;j<s.size();j+=2*(numRows-1))
                    res+=s[j];
            }
            else
            {
                for(int j=i,l=2*(numRows-1)-j;j<s.size() || l<s.size();j+=2*(numRows-1),l+=2*(numRows-1)){
                    if(j<s.size()) res+=s[j];
                    if(l<s.size()) res+=s[l];
                }

            }
        }
        return res;
    }

};



一维二进制优化 时间复杂度nlog(s)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

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

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int value, worth, quantity;
        cin >> value >> worth >> quantity;
        int k=1;
        while(k<quantity)
        {
            cnt++;
            v[cnt]=k*value;
            w[cnt]=k*worth;
            quantity-=k;
            k*=2;
        }
        if(quantity>0)
        {
            cnt++;
            v[cnt]=quantity*value;
            w[cnt]=quantity*worth;
        }

    }
    n=cnt;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}



活动打卡代码 AcWing 5. 多重背包问题 II

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

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

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k=1;
        while(k<s)
        {
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if(s>0)
        {
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }

    }
    n=cnt;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];


    return 0;
}