【思特奇杯·云上蓝桥-算法集训营】第3周

class Solution {
public:
    int fib(int n) {
        if(n<=1)
            return n;
        int lst[n+1];
        lst[0]=0,lst[1]=1;
        for(int i=2;i<=n;i++)
            lst[i]=lst[i-1]+lst[i-2];
        return lst[n];
    }
};

class Solution {
public:
    int tribonacci(int n) {
        if(n<=1)
            return n;
        else if(n==2)
            return 1;
        int lst[n+1];
        lst[0]=0,lst[1]=1,lst[2]=1;
        for(int i=3;i<=n;i++)
            lst[i]=lst[i-3]+lst[i-2]+lst[i-1];
        return lst[n];
    }
};

class Solution {
public:
    int climbStairs(int n) {
        if(n<=3)
            return n;
        int lst[n+1];
        lst[0]=0,lst[1]=1,lst[2]=2,lst[3]=3;
        for(int i=4;i<=n;i++)
            lst[i]=lst[i-1]+lst[i-2];
        return lst[n];
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int n = cost.size();
        int lst[n + 1];
        lst[0] = 0,lst[1] = 0;
        for(int i=2;i<=n;i++)
            lst[i]=min(lst[i-1]+cost[i-1],lst[i-2]+cost[i-2]);
        return lst[n];
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int low = INT_MAX;
        int n=prices.size();
        int result = 0;
        for (int i = 0; i < n; i++) 
        {
            low = min(low, prices[i]);  			// 取最左最小价格
            result = max(result, prices[i] - low); 	// 直接取最大区间利润
        }
        return result;
    }
};

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1=text1.length();
        int len2=text2.length();
        vector> dp(len1+1,vector(len2+1,0));
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++){
                if(text1[i-1]==text2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        return dp[len1][len2];
    }
};

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n;
ll C(int a, int b)
{
    ll res = 1;
    for(ll up = a, down = 1; down <= b; up --, down ++)
    {
        res = res * up / down;
        if(res > n) return res;
    }
    return res;
}
bool check(int j)
{
    ll l = 2 * j, r = max((ll)n, l);
    while(l < r)
    {
        ll k = l + r >> 1;
        if(C(k, j) >= n) 
r = k;
        else 
l = k + 1;
    } 
if(C(r, j) != n)
 return false;
    cout<<(r + 1) * r / 2 + j + 1<>n;
    for(int j=16; ;j--)
        if(check(j))
            break;   
    return 0;
}

#include
#include
#define N 100001 
using namespace std;
vector tree[N];
int T[N];
int dfs(int n)
{
	int k = tree[n].size(); //结点n的子结点数目
	int res1=T[n],res2=0;//res1选择当前结点和它的孙子结点 //res2不选择当前结点，选择它子结点 
	if (tree[n].empty()) 
		return T[n];
	for(int i=0;i>n;
	for(int i=1;i<=n;i++)
		cin>>T[i];
	for(int i=1;i<=n-1;i++)
	{
		cin>>a>>b;
		tree[a].push_back(b); 				//代表a结点的子节点为b 
	}
	int ans=dfs(1);
	cout<

解决方案：

#include 
using namespace std;
int dp[4][10001];
int test(int Floor)
{
	for(int i=1;i<=3;i++)
	   for(int j=1;j<=Floor;j++)
			dp[i][j]=j;               			// 无论有几部手机，运气最差时的测试次数就是楼层的高度                         
	for(int i=2;i<=3;i++)
		for(int j=1;j<=Floor;j++)
			for(int k=1;k>floor;
    test(floor);
    cout< 
 

 
问题描述：K好数 
 

解决方案： 
#include
#include
#define mod	1000000007
using namespace std;
int dp[101][101];						// 好数数组，lst[i][j]，长度为i以j为尾数的情况下 好数的数目 
int main()
{
	int k,l;
	cin>>k>>l; 
	memset(dp,0,sizeof dp);
	for(int j=0;j=2的情况下好数的数目 
		for(int num=0;num