==
第一题
题意：走阶梯，有限制条件：1.只能走一步或者走两步 2.不能连续跳两步
思路：dp[i][j]表示通过跳j步跳到i个的方案数，那么显然dp[i][1]==dp[i][1]+dp[i-1][2]+dp[i-1][1]
而dp[i][2]=dp[i][2]+dp[i-2][1],最后输出就好了，我用的是python，其他语言的话可能要开long long或者大数
第二题：
题意：求左边第一个比a[i]大的a[j]的坐标j，定义为L[i]=j，如果没有则L[i]=0
和右边第一个比a[i]的大的a[k]的坐标k，定义R[i]=k，如果没有则R[i]=0
求最大的R[i]*L[i]
做法：没有什么好i说的，单调栈裸题，建议百度看一下。求出所有的R[i]和L{i],然后求他们的乘积即可
第三题：
题意：给定n长的序列，可以把序列乘以m 倍变成n*m倍的，求最大连续和，且至少包含一个元素
做法：1.求出这个序列本身的最大连续和（这种情况下至少选一个）
2.求包含x个一整个序列（长度为n的）的最大连续和，这种情况下要求序列的和必须大于等于0，并且m大于等于2
将二者求最大值，第一种就是简单的最大连续和，注意一下至少选一个，第二题通过dp求出从左至右包含当前元素的最大连续和（从右至左同理）
那么，答案显然就两者之和加上中间包含的序列总和。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 const ll N=1e5+5; 6 const ll INF=1e17; 7 ll dp[N][2]; 8 ll a[N*2]; 9 int main() 10 { 11 ll n,m,i; 12 scanf("%lld %lld",&n,&m); 13 ll maxsum=0; 14 ll sum=0; 15 ll ans=-INF; 16 for( i=1;i<=n;i++) 17 { 18 scanf("%lld",&a[i]); 19 sum+=a[i]; 20 if(maxsum+a[i]<0) 21 { 22 maxsum=0; 23 } 24 else 25 { 26 maxsum+=a[i]; 27 ans=max(maxsum,ans); 28 } 29 ans=max(ans,a[i]); 30 } 31 dp[n][0]=a[n]; 32 dp[1][1]=a[1]; 33 for(i=2;i<=n;i++) 34 { 35 dp[i][1]=max(dp[i-1][1]+a[i],a[i]); 36 } 37 for(i=n-1;i>=1;i--) 38 { 39 dp[i][0]=max(dp[i+1][0]+a[i],a[i]); 40 } 41 if(sum>0&&m>=2) 42 { 43 ll k=(m-2)*sum; 44 ans=max(k+dp[1][0]+dp[n][1],ans); 45 } 46 if(m>=2) 47 { 48 ans=max(dp[1][0]+dp[n][1],ans); 49 } 50 printf("%lld ",ans); 51 return 0; 52 }
第四题：没写了，据说输出0也有20%，想着三题差不多就跑路了