題目鏈接：點擊查看

題目大意：給出一個長度為 n 的序列，每個元素只由 -1 ， 0 ， 1 組成，現在要求在相鄰兩個元素之間添加一個符號，共添加 n - 1 個符號，符號可以選擇加號或乘號，問如何選擇能使得結果最大

題目分析：第一反應想到用棧模擬，為了讓總結果最大，對于 1 來說肯定加上最優，對于 0 來說，肯定是用于抵消 -1 最優，對于 -1 來說，肯定是與 -1 相乘生成 1 最優，但是有下列兩種情況比較特殊：

-1 1 -1

-1 1 1 -1

這兩種情況的組合顯然答案是 1 更優，但是直接模擬的話是不太容易的，所以我們可以使用 dp 來解決，因為總和上面的規則，我們得出：設 dp[ i ] 是處理到第 i 位為止的答案，那么對于位置 i 來說，最優解肯定是前四項、前三項、前兩項、前一項相乘獲得的最大值加上相應位置轉移而來的，所以直接 O( n ) 維護就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int a[N],dp[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){memset(dp,-inf,sizeof(dp));int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);dp[0]=0;for(int i=1;i<=n;i++){for(int j=max(1,i-4);j<=i;j++){int sum=1;for(int k=j;k<=i;k++)sum*=a[k];dp[i]=max(dp[i],dp[j-1]+sum);}}printf("%d\n",dp[n]);}return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - Gaming with Mia(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。