傳送門
簡(jiǎn)單的線性dpdp。
直接推一推就行了。
貌似三個(gè)狀態(tài)會(huì)卡空間啊。。。
筆者分了兩個(gè)階段考慮狀態(tài)轉(zhuǎn)移。
代碼：

#include<bits/stdc++.h> #define N 5001 #define inf 0x3f3f3f3f using namespace std; char xxx; int n,t,f[N][N],s[N],b[N],ans=0; char yyy; int main(){memset(f,-inf,sizeof(f));scanf("%d%d",&n,&t),f[0][0]=0;for(int i=1;i<=n;++i)scanf("%d",&s[i]);for(int i=1;i<=n;++i)scanf("%d",&b[i]);for(int i=1;i<=n;++i){if(i>=t){for(int j=1;j<t;++j){if(f[i-1][j]!=-inf)f[i][j]=f[i-1][j]-s[i];if(f[i-1][j-1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j-1]+s[i]);}if(f[i-1][t-1]!=-inf)f[i][0]=f[i-1][t-1]+s[i]+b[i];if(f[i-1][0]!=-inf)f[i][0]=max(f[i][0],f[i-1][0]-s[i]);}else{for(int j=1;j<i;++j){if(f[i-1][j]!=-inf)f[i][j]=f[i-1][j]-s[i];if(f[i-1][j-1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j-1]+s[i]);}f[i][i]=f[i-1][i-1]+s[i];if(f[i-1][0]!=-inf)f[i][0]=f[i-1][0]-s[i];}for(int j=0;j<t;++j)ans=max(ans,f[i][j]);}cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ldxcaicai/p/9738383.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的2018.08.16 洛谷P2029 跳舞（线性dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。