T13P1833 樱花 - 洛谷在这里主要是学到了一次背包和若干次背包的区别若干次就是在前面套一个n次的循环。#includeiostream #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 i1;i2;i){ cins; 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); } } dttim[2]-tim[1]; //coutdtendl; cinn; for(i64 i1;in;i){ cint[i]c[i]p[i]; } for(i64 i1;in;i){ if(p[i]0){ for(i64 jt[i];jdt;j){ dp[j]max(dp[j],dp[j-t[i]]c[i]); } }else{ for(i64 tms1;tmsp[i];tms){ for(i64 jdt;jt[i];j--){ dp[j]max(dp[j],dp[j-t[i]]c[i]); } } } } coutdp[dt]; return 0; }T14P2340 [USACO03FALL] Cow Exhibition G - 洛谷我已急哭这种思维到底是怎么练出来的#includeiostream #includecstring #define i64 long long #define py 400000 using namespace std; i64 n,s[405],f[405],dp[1000005],ans0; int main(){ cinn; for(i64 i1;in;i){ cins[i]f[i]; } //dp[i][j]前i只奶牛智商为j时的情商值。 memset(dp,-999999,sizeof(dp)); dp[py]0;//偏移量 for(i64 i1;in;i){ if(s[i]0){ for(i64 j2*py;js[i];j--){ dp[j]max(dp[j],dp[j-s[i]]f[i]); } }else{ for(i64 j0;j2*pys[i];j){ dp[j]max(dp[j],dp[j-s[i]]f[i]); } } } for(i64 jpy;j2*py;j){ if(dp[j]0){ ansmax(ans,dp[j]j-py); } } coutans; return 0; }T15P1541 [NOIP 2010 提高组] 乌龟棋 - 洛谷感觉我这题解质量极速降低因为我真的什么都不会呜呜呜。。。这哥们写的巨详细P1541 乌龟棋 - 洛谷专栏dp[i][j][k][t]表示你出了i张爬行牌1j张爬行牌2k张爬行牌3t张爬行牌4时的得分#includeiostream #includecstring #define i64 long long #define py 400000 using namespace std; i64 n,m,x; i64 a[355],b[10],dp[45][45][45][45],ans0; int main(){ cinnm; for(i64 i1;in;i){ cina[i]; } for(i64 i1;im;i){ cinx; b[x]; } dp[0][0][0][0]a[1]; for(i64 i0;ib[1];i){ for(i64 j0;jb[2];j){ for(i64 k0;kb[3];k){ for(i64 t0;tb[4];t){ i64 r1ij*2k*3t*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]); } } } } coutdp[b[1]][b[2]][b[3]][b[4]]; return 0; }T16P4310 绝世好题 - 洛谷这是最纯粹的暴力dp都能过80%。#includeiostream #includecstring #define i64 long long using namespace std; i64 n; i64 a[100005],dp[100005]; int main(){ cinn; for(i64 i1;in;i){ cina[i]; if(a[i]!0) dp[i]1; else dp[i]0; } for(i64 i1;in;i){ for(i64 j1;ji;j){ if((a[i]a[j])!0){ //couta[i] a[j]endl; dp[i]max(dp[i],dp[j]1); } } } coutdp[n]; return 0; }#includeiostream #includecstring #define i64 long long using namespace std; i64 n,x,ans0; i64 dp[55]; int main(){ cinn; for(i64 i1;in;i){ cinx; i64 mx0; for(i64 j0;j32;j){ if(x(1LLj)){ mxmax(mx,dp[j]); } } for(i64 j0;j32;j){ if(x(1LLj)){ dp[j]mx1; } } /*for(i64 j0;j3;j){ coutdp[j] ; } coutendl;*/ } for(i64 j0;j32;j){ ansmax(ans,dp[j]); } coutans; return 0; }
