当前位置：首页 > news >正文

洛谷【动态规划2】线性状态动态规划题解13-16 详细易懂不炫技

news 2026/8/13 12:54:07

T13

P1833 樱花 - 洛谷

在这里主要是学到了一次背包和若干次背包的区别，若干次就是在前面套一个n次的循环。

#include<iostream> #define i64 long long using namespace std; string s; i64 tim[3],dt; i64 n,t[10005],c[10005],p[10005],dp[1000005]; void dfs(i64 i, i64 j); int main(){ for(i64 i=1;i<=2;i++){ cin>>s; if(s[1]==':'){ tim[i]=(s[0]-'0')*60+(s[2]-'0')*10+(s[3]-'0'); }else if(s[2]==':'){ tim[i]=((s[0]-'0')*10+(s[1]-'0'))*60+(s[3]-'0')*10+(s[4]-'0'); } } dt=tim[2]-tim[1]; //cout<<dt<<endl; cin>>n; for(i64 i=1;i<=n;i++){ cin>>t[i]>>c[i]>>p[i]; } for(i64 i=1;i<=n;i++){ if(p[i]==0){ for(i64 j=t[i];j<=dt;j++){ dp[j]=max(dp[j],dp[j-t[i]]+c[i]); } }else{ for(i64 tms=1;tms<=p[i];tms++){ for(i64 j=dt;j>=t[i];j--){ dp[j]=max(dp[j],dp[j-t[i]]+c[i]); } } } } cout<<dp[dt]; return 0; }

T14

P2340 [USACO03FALL] Cow Exhibition G - 洛谷

我已急哭，这种思维到底是怎么练出来的？

#include<iostream> #include<cstring> #define i64 long long #define py 400000 using namespace std; i64 n,s[405],f[405],dp[1000005],ans=0; int main(){ cin>>n; for(i64 i=1;i<=n;i++){ cin>>s[i]>>f[i]; } //dp[i][j]前i只奶牛智商为j时的情商值。 memset(dp,-999999,sizeof(dp)); dp[py]=0;//偏移量 for(i64 i=1;i<=n;i++){ if(s[i]>=0){ for(i64 j=2*py;j>=s[i];j--){ dp[j]=max(dp[j],dp[j-s[i]]+f[i]); } }else{ for(i64 j=0;j<=2*py+s[i];j++){ dp[j]=max(dp[j],dp[j-s[i]]+f[i]); } } } for(i64 j=py;j<=2*py;j++){ if(dp[j]>0){ ans=max(ans,dp[j]+j-py); } } cout<<ans; return 0; }

T15

P1541 [NOIP 2010 提高组] 乌龟棋 - 洛谷

感觉我这题解质量极速降低，因为我真的什么都不会呜呜呜。。。

这哥们写的巨详细P1541 乌龟棋 - 洛谷专栏

dp[i][j][k][t]表示你出了i张爬行牌1，j张爬行牌2，k张爬行牌3，t张爬行牌4时的得分

#include<iostream> #include<cstring> #define i64 long long #define py 400000 using namespace std; i64 n,m,x; i64 a[355],b[10],dp[45][45][45][45],ans=0; int main(){ cin>>n>>m; for(i64 i=1;i<=n;i++){ cin>>a[i]; } for(i64 i=1;i<=m;i++){ cin>>x; b[x]++; } dp[0][0][0][0]=a[1]; for(i64 i=0;i<=b[1];i++){ for(i64 j=0;j<=b[2];j++){ for(i64 k=0;k<=b[3];k++){ for(i64 t=0;t<=b[4];t++){ i64 r=1+i+j*2+k*3+t*4; if(i!=0) dp[i][j][k][t]=max(dp[i][j][k][t], dp[i-1][j][k][t]+a[r]); if(j!=0) dp[i][j][k][t]=max(dp[i][j][k][t], dp[i][j-1][k][t]+a[r]); if(k!=0) dp[i][j][k][t]=max(dp[i][j][k][t], dp[i][j][k-1][t]+a[r]); if(t!=0) dp[i][j][k][t]=max(dp[i][j][k][t], dp[i][j][k][t-1]+a[r]); } } } } cout<<dp[b[1]][b[2]][b[3]][b[4]]; return 0; }

T16

P4310 绝世好题 - 洛谷

这是最纯粹的暴力dp，都能过80%。

#include<iostream> #include<cstring> #define i64 long long using namespace std; i64 n; i64 a[100005],dp[100005]; int main(){ cin>>n; for(i64 i=1;i<=n;i++){ cin>>a[i]; if(a[i]!=0) dp[i]=1; else dp[i]=0; } for(i64 i=1;i<=n;i++){ for(i64 j=1;j<i;j++){ if((a[i]&a[j])!=0){ //cout<<a[i]<<' '<<a[j]<<endl; dp[i]=max(dp[i],dp[j]+1); } } } cout<<dp[n]; return 0; }

#include<iostream> #include<cstring> #define i64 long long using namespace std; i64 n,x,ans=0; i64 dp[55]; int main(){ cin>>n; for(i64 i=1;i<=n;i++){ cin>>x; i64 mx=0; for(i64 j=0;j<=32;j++){ if(x&(1LL<<j)){ mx=max(mx,dp[j]); } } for(i64 j=0;j<=32;j++){ if(x&(1LL<<j)){ dp[j]=mx+1; } } /*for(i64 j=0;j<=3;j++){ cout<<dp[j]<<' '; } cout<<endl;*/ } for(i64 j=0;j<=32;j++){ ans=max(ans,dp[j]); } cout<<ans; return 0; }

查看全文

http://www.jsqmd.com/news/1385114/