==
第一題
題意：走階梯，有限制條件：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\n",ans); 51 return 0; 52 }
第四題：沒寫了，據說輸出0也有20%，想著三題差不多就跑路了
浙公網安備 33010602011771號