Summer Vacation Algorithm 7.15, Day14

Summer Vacation Algorithm 7.15, Day14

Linear DP

The teacher of this special school has explained it in great detail, so it is very easy to write.

Looking forward to more dp topics

first question

Maximum sum of consecutive subarrays

Maximum field sum, one of the classic dp problems:

Two cases, one: the latter number is a negative number two: the latter number is a positive number.

class Solution {
const int MAXX=1000008;
public:
    int maxSubArray(vector<int>& nums) {
        int dp[MAXX];
        dp[0]=nums[0];
        int MAX=dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            MAX=max(MAX,dp[i]);
        }
        return MAX;
    }
};

Question 2

longest increasing subsequence

It is also one of the classic dp questions and was also tested as a final exam. It should be very simple, not much to say.

class Solution {
const int MAXX=10000008;
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[MAXX];
        dp[0]=1;
        int maxlen;
        int maxx=dp[0];
        for(int i=1;i<nums.size();i++){
            maxlen=0;
            for(int j=i-1;j>=0;j--){
                if(nums[j]<nums[i]&&dp[j]>maxlen){
                    maxlen=dp[j];
                }
            }
            dp[i]=maxlen+1;
            if(dp[i]>maxx){
                maxx=dp[i];
            }
        }
        return maxx;
    }
};

Question 3

Count the number of ways to place the house

class Solution {
const int MAXX=1e9+7;
public:
    int countHousePlacements(int n) {
        long long dp[n+5];
        dp[0]=2;
        dp[1]=3;
        if (n == 1) {
            return dp[n-1]*dp[n-1];
        }
        if (n == 2) {
            return dp[n-1] * dp[n-1];
        }
        for (int i = 2; i < n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2])%MAXX;
        }
        return (dp[n-1] * dp[n-1])%MAXX ;
    }
};

Question 4

Computer Game

The problem of walking the maze, but this maze has only two lines, so it is very simple, although he can walk horizontally, vertically, and diagonally. I just need to judge if the wall in front of it is sealed. That is: a[0][j]=='1'&&a[1][j]=='1'the wall is blocked, and no matter how you go, you will definitely not be able to go.

#include <bitsdc++.h>
using namespace std;
const int MAXX=1e5+5;
char a[2][MAXX];
bool solve(int n)
{
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    bool flag=true;
    for(int j=0; j<n; j++)
    {
        if(a[0][j]=='1'&&a[1][j]=='1')
        {
            flag=false;
            break;
        }
    }
    return flag;
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int n;
        cin>>n;
        bool result=solve(n);
        if(result){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Leave a Comment

Your email address will not be published. Required fields are marked *