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

第一题斐波那切数
class Solution {
public int fib(int N) {
if(N <= 1) return N;
int first = 0, second = 1;
for(int i = 0; i < N - 1; i++){
int sum = first + second;
first = second;
second = sum;
}
return second;
}
}

第二题
class Solution {
public:
int tribonacci(int n) {
int a[100]={0,1,1};
for(int i = 3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2]+a[i-3];
}
return a[n];
}
};

第三题爬楼梯

public static int climbStairs(int n) {
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return climbStairs(n-1)+climbStairs(n-2);
}

第四题使用最小花费爬楼梯
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
//特判
if (cost.empty()) return 0;
if (cost.size() == 1) return cost[0];
if (cost.size() == 2) return min(cost[0], cost[1]);
vector dp(cost.size()+1);
//初始值
dp[0] = 0;
dp[1] = 0;
//状态转移
for (int i=2;i<=cost.size();i++)
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};

第五题买入股票的最佳时机

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int getmin(int *prices,int size)
{
int i = 0;
int tmp = 0;
tmp = prices[0];
for (i=1;i {
if (prices[i] < tmp)
{
tmp = prices[i];
}
}

return tmp;

}

int maxProfit(int* prices, int pricesSize)
{
int dp[200000] = {0};
int i = 0;
int tmp = 0;
dp[0] = 0;
dp[1] = 0;

if (pricesSize == 1)
{
    return 0;
}

tmp = prices[0];
for (i = 2;i <= pricesSize;i++)
{
    //tmp = getmin(prices,i-1);//这里每一次都求的话显然没有必要且重复计算，导致超时
    tmp = min(tmp,prices[i-1]);
	printf("%dn",tmp);
    dp[i] = max(dp[i-1],prices[i-1] - tmp);
}

return dp[pricesSize];

}

第六题最长公共子序列
//最长公共子序列
#include
#include
#include
#define MAX 1001
using namespace std;
int dp[MAX][MAX];
int main()
{
int N;
cin >> N;
while(N–)
{
string a,b;
cin >> a >> b;
memset(dp,0,sizeof(dp));
int len_a=a.size(),len_b=b.size();
for(int i=0;i {
for(int j=0;j {
if(a.at(i)==b.at(j))
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
}
}
cout << dp[len_a][len_b] << endl;
a.clear();
b.clear();
}
return 0;
}

第七题杨辉三角形
#include
#include
using namespace std;

int main(){
const int n=11;//变量n在此处起到了限制输出行数的作用，可优化成用户输入
int i,j,a[n][n];

//使第一列和对角线元素的值为1
for (i=1;i a[i][i]=1;//使最右侧边全为1
a[i][1]=1;//使最左侧边全为1
}

//从第三行开始处理
for (i=3;i for (j=2;j<=i-1;j++) //j始终慢i一步
a[i][j]=a[i-1][j-1]+a[i-1][j];//每个数等于它上方两数之和，如a32=a21+a22

//输出数组各元素的值
for (i=1;i for (j=1;j<=i;j++) //利用j将每一行的数据全部输出
cout< }
cout< return 0;
}

第八题节点选择

int edge;

int next;

e[++M].edge = ee;           ///边的终点

e[M].next = head[s];        ///邻边

head[s] = M;                ///当前边

dp[s][0]=val[s];

dp[s][1]=0;

for(int i=head[s];i!=-1;i=e[i].next)

    int u=e[i].edge;

    if(v[u]==0)

        v[u]=1;

        dfs(u);

        dp[s][0]+=dp[u][1];

        dp[s][1]+=max(dp[u][1],dp[u][0]);

        v[u]=0;

int s,e;

int ans=0;

memset(head,-1,sizeof(head));

memset(dp,0,sizeof(dp));

memset(v,0,sizeof(v));

cin>>N;

for(int i=1;i<=N;i++)

    cin>>val[i];

for(int i=1;i  {  
      cin>>s>>e;  
      add(s,e);  
      add(e,s);  
  }  
  v[1]=1;  
  dfs(1);  
  v[1]=0;  
  ans=max(dp[1][0],dp[1][1]);  
  cout<
  return 0;  
 }

第九题耐摔指数

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
int f2[105],f3[105];
int main(){
int n;
while(~scanf("%d",&n)){
int i=0;
while(f3[i] i++;
f2[i]=f2[i-1]+i;//这里i本身就++了，所以不用加一了
f3[i]=f3[i-1]+f2[i-1]+1;
}
cout< }
return 0;
}

第十题 k好数

#include
#include
using namespace std;
int dp[1000][1000];
const int MOD=1000000007;
int main()
{
int sum=0;
int CountK(int,int,int);
int K,L;
cin>>K>>L;
if(K1&&L1) //这里对1位1进制的个数为啥不是1表示不理解
cout<<0< else if(K>1&&L==1)//1位的K进制的K好数总数就是K个
cout< else if(L>1)
cout< return 0;
}
int CountK(int length,int range,int sum)
{
for(int i=1;i {
dp[0][i]=1;
}
for(int i=1;i {
for(int j=0;j {
for(int k=0;k {
if(abs(j-k)!=1)
{
if((j-1)0&&k0)//排除首位为0的情况
continue;
dp[i][j]=dp[i][j]+dp[i-1][k];
dp[i][j]%=MOD;
}
}
}
}
for(int i=0;i {
sum+=dp[length-1][i];
sum%=MOD;
}
return sum;
}

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

C/C++/C#相关栏目本月热门文章