今天在洛谷上刷dp，忽然冒出一道求最大字段和的問題，然后忘了瞬間忘了這是dp，幾分鐘一個貪心出來了成功ac，忽然想起自己在作dp，于是乖乖刷dp。

這個可能很多人都會但是今天有4種解法哦，本人只嘗試了3種解法。

NO.1:明顯一個貪心一個sum求當前的累加和如果小于0就清零，繼續累加并不斷去max即可。

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<iomanip> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> using namespace std; inline long long read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int n; int a[200009]; int ans=0; int maxx=-1111111; int main() {//freopen("1.in","r",stdin);n=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++){ans+=a[i];if(ans>maxx){maxx=ans;}if(ans<0)ans=0;}printf("%d\n",maxx);return 0; } View Code

NO.2:說是要練dp嘛，然后點開題解看dalao們的dp，f[i]=max(f[i-1],a[i]);這樣最大值在f[i]之中，最后找max即可。

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<iomanip> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> using namespace std; inline long long read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int n; int a[200009]; int f[200009]; int ans=-1111111; int main() { // freopen("1.in","r",stdin);n=read();for(int i=1;i<=n;i++){a[i]=read();f[i]=max(f[i-1]+a[i],a[i]);ans=max(f[i],ans);}cout<<ans<<endl;return 0; } View Code

NO.3:題解之中有一個分治的想法，十分巧妙的把所有情況遞歸出來從而求解。在每一個區間之中取max即可。

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<iomanip> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> using namespace std; inline long long read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } const int maxn=-1111111; int n; int a[200009]; int bwy(int x,int y) {if(x==y)return a[x];int mid=(x+y)>>1;int maxx=maxn,maxx1=maxn,sum=0;for(int i=mid;i>=x;i--){sum+=a[i];maxx=max(maxx,sum);}sum=0;for(int i=mid+1;i<=y;i++){sum+=a[i];maxx1=max(maxx1,sum);}return max(max(bwy(x,mid),bwy(mid+1,y)),maxx+maxx1); } int main() {//freopen("1.in","r",stdin);n=read();for(int i=1;i<=n;i++)a[i]=read();printf("%d\n",bwy(1,n));return 0; } View Code

這個就比較難理解了，要多看看。

No.4：有大神用的是線段樹來維護，tql，我不想打線段樹代碼就沒有了。。。

下面回到了本校oj看起來以前過得題想要再想想。求最大連續子矩陣累加和，這個就要壓縮維度了。

仔細想想，我可以先把每一列的前綴和全部求出來進行維度的壓縮，然用一個一維數組來表示第幾列從第i行到第j行的累加，十分巧妙的思想，我想了十幾分鐘才搞懂。這樣的話就可以便利到每一個矩陣了，十分巧妙！！！

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<iomanip> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> using namespace std; inline long long read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } const int maxn=505; int n,a[maxn][maxn],tmp[maxn],maxx=-1100000,ans=0; int main() {freopen("1.in","r",stdin);n=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){maxx=read();a[i][j]=a[i-1][j]+maxx;//前綴和 }maxx=-1100000;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){ans=0;//注意便利下一個矩陣的時候ans要清零。for(int k=1;k<=n;k++){tmp[k]=a[j][k]-a[i-1][k];ans+=tmp[k];if(ans>maxx)maxx=ans;if(ans<0)ans=0;}}}printf("%d\n",maxx);return 0; } View Code

然后還有很難的三維壓縮qwq真不想寫。。。

三維的壓縮，但首先要看懂題。

看著學長的代碼自慢慢干，發現書上的方法并不是很優，還不如和第二題一樣進行壓縮。

a[i][j][k]+=a[i-1][j][k]；壓縮高度——c[k][u]=a[j][k][u]-a[i-1][k][u];再取任意寬度和長度的立方體塊壓到一個二維數組之中實現任意立方體小塊的拿取，

這樣就可以了，c[k][u]+=c[k][u-1];壓縮寬度這樣就和上一題一樣開始壓縮二維數組，取任意矩陣的和。b[x]=c[x][u]-c[x][k-1];——這樣壓縮到一維的數組里面取任意的矩陣然后用求最大字段和就行了。是很難理解的表示不想手動模擬一遍。。。

代碼：

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<iomanip> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> using namespace std; inline long long read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int a[101][101][101],c[101][101],b[101],ans,maxx=-1000000; int n,h,m; int main() {//freopen("1.in","r",stdin);h=read();m=read();n=read();for(int i=1;i<=h;i++)for(int j=1;j<=m;j++)for(int k=1;k<=n;k++)a[i][j][k]=read(),a[i][j][k]+=a[i-1][j][k];for(int i=1;i<=h;i++)for(int j=i;j<=h;j++){for(int k=1;k<=m;k++)for(int u=1;u<=n;u++){c[k][u]=a[j][k][u]-a[i-1][k][u];c[k][u]+=c[k][u-1];}for(int k=1;k<=n;k++)for(int u=k;u<=n;u++){ans=0;for(int x=1;x<=m;x++){ b[x]=c[x][u]-c[x][k-1];ans+=b[x];if(ans>maxx)maxx=ans;if(ans<0)ans=0;}}}printf("%d\n",maxx);return 0; } View Code

大功告成啦。。。

如果你的青春感到迷茫，那就對了，因為誰的青春不迷茫。

b[x]=c[x][u]-c[x][k-1];

轉載于:https://www.cnblogs.com/chdy/p/9741603.html

總結

以上是生活随笔為你收集整理的压缩维度oj P1173+P1174+P1164的全部內容，希望文章能夠幫你解決所遇到的問題。

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