A---母牛的故事
题目大意：第一年有一头母牛，每年年初母牛生小母牛，小母牛第四个年头可以开始生小牛。
问第n年有多少头牛。
题解：
(1)列出前几项来找规律（2）第i年牛的数量=第i-1年牛的数量+（新出生的牛的数量=第i-3年牛的数量）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; int dp[60]; int main() { dp[1]=1;dp[2]=2;dp[3]=3;dp[4]=4; for(int i=5;i<=60;i++) dp[i]=dp[i-1]+dp[i-3]; while(scanf("%d",&n)&&n) cout<<dp[n]<<endl; return 0; }
B---Cow Bowling
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
数字金字塔 从上往下走只能走左右求到最后一层的最大值
n<=350 搜索不行呀 从上往下推
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; int ans; int a[360][360]; int f[360][360]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } f[1][1]=a[1][1]; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j]; } } for(int i=1;i<=n;i++)ans=max(ans,f[n][i]); cout<<ans<<endl; return 0; }
C---Sumsets
题目大意:
一个数分成几个2的x次方的和的方案数
如：
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
题解：
（1）暴力
（2）打表找规律 找出递推式
a、如果i是奇数，那么a[i]=a[i-1]；在i-1的数的方法数+1
b、如果i是偶数，那么a[i]=a[i-1]+a[i/2];
如果i是偶数 在i-1的数+1 i/2的方案数里都*2；
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define M 1000000 using namespace std; int n,p; int ans; int b[100]; void dfs(int x,int now,int sum) { if(sum>now) return ; if(sum==now) { ans++; return; } for(int i=x;i>=0;i--) //i>=0不是i { dfs(i,now,sum+b[i]); } } int main() { b[0]=1; for(int i=1;i;i++) { b[i]=b[i-1]*2; if(b[i]>M) { p=i;break; } } for(int i=1;i<=20;i++) { ans=0; dfs(p,i,0); cout<<ans<<endl; } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define M 1000000000 using namespace std; int n; int a[1000001]; int main() { scanf("%d",&n); a[1]=1;a[2]=2;a[3]=2;a[4]=4; for(int i=5;i<=n;i++) { if(i%2) a[i]=a[i-1]%M; else a[i]=(a[i-2]+a[i/2])%M; } cout<<a[n]; return 0; }
原文：https://www.cnblogs.com/zzyh/p/11701267.html