\u770b\u8d77\u6765\u662f\u4e00\u9053\u5f88\u7b80\u5355\u7684\u9898\uff0c\u4f46\u662f\u7ec6\u8282\u5de8\u591a\uff0c\u6d88\u8017\u4e86\u6211\u5927\u91cf\u7684\u63d0\u4ea4\u6b21\u6570\u3002\u5982\u679c\u662f\u6bd4\u8d5b\u6211\u6015\u4e0d\u662f\u51c9\u4e86\u3002<\/p>\n
\u5f88\u663e\u7136\u662f\u4e00\u9053DP\u9898\u3002
\n\u5f88\u5bb9\u6613\u53ef\u4ee5\u60f3\u5230\u7684\u662f\u66b4\u529b\u679a\u4e3e\uff0c\u7136\u800c\u8fd9\u6837\u505a\u7684\u590d\u6742\u5ea6\u662fO(n^2*n^2k)\u7684\uff0c\u5f88\u5f88\u5f88\u5f88\u663e\u7136\u53ef\u4ee5\u53d1\u73b0\u662f\u4e0d\u53ef\u884c\u7684\u3002
\n\u89c2\u5bdf\u6570\u636e\u8303\u56f4\uff0c\u6211\u4eec\u53ef\u4ee5\u6ce8\u610f\u5230\uff0c m<=2\uff0c\u56e0\u6b64\u5f88\u5bb9\u6613\u53ef\u4ee5\u60f3\u5230\u72b6\u538bDP\u3002
\n\u5177\u4f53\u6765\u8bf4\uff0c\u5f53m==2\u65f6\uff0c\u7528f[i][j][l]\u8868\u793a\uff0c\u5f53\u524d\u5904\u4e8e\u7b2ci\u884c\uff0c\u7b2ci\u884c\u7684\u72b6\u6001\u4e3aj\uff0c\u5df2\u7ecf\u4f7f\u7528\u4e86l\u4e2a\u5b50\u77e9\u9635\u65f6\uff0c\u6700\u5927\u7684\u548c\u3002
\n\u5219\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u662f\uff1a<\/p>\n
f[i][0][l]=Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l]));\r\nf[i][1][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l]))+b[i];\r\nf[i][2][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l]))+a[i];\r\nf[i][3][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l]))+a[i]+b[i];<\/code><\/pre>\n\u5e76\u4e14\u6211\u4eec\u5f88\u5bb9\u6613\u53ef\u4ee5\u5f97\u5230\u8fb9\u754c\u6761\u4ef6\uff0c\u5373\uff1a<\/p>\n
f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][1]=a[1]+b[1];<\/code><\/pre>\n\u53e6\u5916\u9700\u8981\u8003\u8651m==1\u7684\u60c5\u51b5\uff0c\u4e8b\u5b9e\u4e0a\u8fd9\u79cd\u60c5\u51b5\u66f4\u5bb9\u6613\u8003\u8651\uff1a\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u662f\uff1a<\/p>\n
f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);\r\nf[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; <\/code><\/pre>\n\u521d\u59cb\u5316f[1][0][0]=0,f[1][1][1]=a[1];<\/p>\n
\u7136\u800c\u4ea4\u4e0a\u53bb\u5168wa
\n\u56de\u5934\u8003\u8651\u8fd9\u4e2a\u95ee\u9898\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\u4e00\u4e2a\u5f88\u5c34\u5c2c\u7684\u4e8b\u60c5\uff1a\u5f53\u4e0a\u4e00\u884c\u4e24\u4e2a\u53d6\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5e76\u4e0d\u77e5\u9053\u5b83\u5230\u5e95\u662f\u300c\u4e24\u5217\u5206\u522b\u53d6\u300d\u8fd8\u662f\u300c\u4e24\u5217\u4e00\u8d77\u53d6\u300d\u3002
\n\u56e0\u6b64\uff0c\u5bf9\u4e8e11\u7684\u72b6\u6001\uff0c\u6211\u4eec\u5e94\u5f53\u62c6\u6210\u4e24\u4e2a\u90e8\u5206\uff1a
\nf[i][3][l]\u8868\u793a\u4e0a\u4e00\u884c\u7684\u4e24\u5217\u662f\u5206\u522b\u53d6\u7684\u3002\u4e8e\u662f\u5f97\u5230\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u3002
\nf[i][4][l]\u8868\u793a\u4e0a\u4e00\u884c\u7684\u4e24\u5217\u662f\u5408\u5728\u4e00\u8d77\u53d6\u7684\u3002<\/p>\n
f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);\r\nf[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];\r\nf[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];\r\nf[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];\r\nf[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];<\/code><\/pre>\n\u7136\u800c\u8fd9\u6837\u5b50\u8fd8\u662f\u5168WA\u3002
\n\u4ed4\u7ec6\u89c2\u5bdf\u4e00\u4e0b\u6211\u4eec\u7684\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff0c\u6211\u4eec\u53d1\u73b0\u5b58\u5728\u4e00\u4e9bl-2\u7684\u72b6\u6001\uff0c\u90a3\u4e48\u6211\u4eec\u5e94\u8be5\u5206\u4e24\u7c7b\u8ba8\u8bba\uff1al==1\u6216l>=2.
\n\u8fd9\u6837\u5927\u6982\u5c31\u80fd\u901a\u8fc7\u4e86\u3002<\/p>\n
#include\r\n#include\r\n#include\r\nusing namespace std;\r\n#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))\r\nint n,m,k,f[105][5][15],a[105],b[105];\r\n\r\nvoid slv1(){\r\n for(int i=1;i<=n;++i){\r\n scanf(\"%d\",&a[i]);\r\n }\r\n f[1][0][0]=0,f[1][1][1]=a[1];\r\n for(int i=1;i<=n;++i){\r\n f[i][0][0]=f[i][1][0]=0;\r\n for(int l=1;l<=k;++l){\r\n f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);\r\n f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; \r\n }\r\n }\r\n int ans=-0x3f3f3f3f;\r\n printf(\"%d\",Max(f[n][0][k],f[n][1][k]));\r\n return;\r\n}\r\nvoid slv2(){\r\n for(int i=1;i<=n;++i){\r\n scanf(\"%d%d\",&a[i],&b[i]);\r\n }\r\n f[0][0][0]=0;\r\n f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][2]=a[1]+b[1],f[1][4][1]=a[1]+b[1];\r\n for(int i=1;i<=n;++i){\r\n f[i][0][0]=f[i][1][0]=f[i][2][0]=f[i][3][0]=f[i][4][0]=0;\r\n for(int l=1;l<=k;++l){\r\n f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);\r\n f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];\r\n f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];\r\n f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];\r\n if(l<2){\r\n continue;\r\n }\r\n f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];\r\n }\r\n }\r\n \/*\r\n for(int i=1;i<=n;++i){\r\n for(int l=0;l<=k;++l){\r\n for(int j=0;j<5;++j){\r\n printf(\"%d \",f[i][j][l]);\r\n }\r\n puts(\"\");\r\n }\r\n puts(\"\");\r\n }*\/\r\n int ans=-0x3f3f3f3f;\r\n for(int i=0;i<5;++i){\r\n ans=Max(ans,f[n][i][k]);\r\n }\r\n printf(\"%d\",ans);\r\n}\r\nvoid init(){\r\n\tscanf(\"%d%d%d\",&n,&m,&k);\r\n\tmemset(f,-1,sizeof(f));\r\n\tif(m==1){\r\n\t slv1();\r\n }\r\n if(m==2){\r\n slv2();\r\n }\r\n}\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u770b\u8d77\u6765\u662f\u4e00\u9053\u5f88\u7b80\u5355\u7684\u9898\uff0c\u4f46\u662f\u7ec6\u8282\u5de8\u591a\uff0c\u6d88\u8017\u4e86\u6211\u5927\u91cf\u7684\u63d0\u4ea4\u6b21\u6570\u3002\u5982\u679c\u662f\u6bd4\u8d5b\u6211\u6015\u4e0d\u662f\u51c9\u4e86\u3002 \u5f88\u663e\u7136\u662f\u4e00\u9053DP\u9898\u3002 … <\/p>\n