孩子们,我回来了
先看题
这很明显就是动态规划啊
先打个表
不难发现,
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
敲代码,把别的补上就好了
#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;int main(){unsigned long long dp[65]={0,1,2,4};for(int i=4;i<61;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];} int n;cin>>n;cout<<dp[n];return 0;
}
可以看见,半江瑟瑟半江红
主要是输入的时候,爆了!
dp[36]=2082876103;
dp[37]=3831006429;
INT_MAX=2147483647;
3831006429>2147483647,因此需要救一下,用long long
#include<bits/stdc++.h>
using namespace std;int main(){unsigned long long dp[65]={0,1,2,4};for(int i=4;i<61;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];} int n;cin>>n;cout<<dp[n];return 0;
}
OK,也是直接过了