\u4e00\u9053\u4f18\\(d\\acute{u}\\)\u79c0\\(li\\acute{u}\\)\u7684\u671f\u671bDP\u3002
\n\u7b80\u8ff0\u9898\u610f\uff1a
\n\u539f\u6709\u4e00\u4e2a\u5305\u62ec\\(n\\)\u4e2a\u8282\u70b9\u7684\u8def\u5f84\uff0c\u4f60\u53ef\u4ee5\u7528\\(m\\)\u6b21\u64cd\u4f5c\uff0c\u6bcf\u4e00\u6b21\u64cd\u4f5c\u53ef\u4ee5\u628a\u7b2c\\(i\\)\u4e2a\u8282\u70b9\u4ece\\(c_{i}\\)\u6362\u5230\\(b_{i}\\)\u3002
\n\u5bf9\u4e8e\u6bcf\u4e00\u6b21\u64cd\u4f5c\uff0c\u6709\\(p_{i}\\)\u7684\u6982\u7387\u6210\u529f\u3002\u6c42\u6700\u4f18\u51b3\u7b56\u4e0b\u8def\u5f84\u957f\u5ea6\u7684\u671f\u671b\u3002<\/p>\n
\u9996\u5148\u8003\u8651\u5230\u662f\u7a20\u5bc6\u56fe\uff0c\u6545\u8003\u8651\u7528\u90bb\u63a5\u77e9\u9635\u6765\u5904\u7406\u3002\u4e0d\u8fc7\u9700\u8981\u6ce8\u610f\u8bfb\u5165\u65f6\u5e94\u5f53\u53d6\u8f83\u5c0f\u503c\uff0c\u4ee5\u53ca\u6bcf\u4e2a\u70b9\u5230\u5176\u672c\u8eab\u7684\u8ddd\u79bb\u4e3a\\(0\\)
\n\u9996\u5148\u7528\\(Floyd\\)\u9884\u5904\u7406\u51fa\u6240\u6709\u70b9\u4e4b\u95f4\u7684\u8ddd\u79bb\u3002\u7136\u540e\u6211\u4eec\u5b9a\u4e49\\(f_{i,j,k}\\)\u8868\u793a\uff0c\u5f53\u524d\u5728\u51b3\u5b9a\u7b2c\\(i\\)\u4e2a\u8282\u70b9\uff0c\u5df2\u7ecf\u4f7f\u7528\u4e86\\(j\\)\u6b21\u673a\u4f1a\uff0c\u5f53\u524d\u9009\u62e9\u4e3a\\(k\\)\u65f6\u7684\u671f\u671b\u8def\u5f84\u957f\u5ea6\u3002
\n\u90a3\u4e48\u6211\u4eec\u8003\u8651\u8f6c\u79fb\u3002
\n\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u72b6\u6001\uff0c\u6211\u4eec\u6709\u4e24\u79cd\u9009\u62e9\uff1a\u4f7f\u7528\u673a\u4f1a\u6216\u8005\u4e0d\u4f7f\u7528\u673a\u4f1a\u3002\u6545\u800c\u6211\u4eec\u5c1d\u8bd5\u63a8\u7406\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a
\n\u9996\u5148\uff0c\u5982\u679c\u4e0d\u4f7f\u7528\u673a\u4f1a\u7684\u8bdd\uff0c\u6709\u4e24\u79cd\u60c5\u51b5\u53ef\u4ee5\u8f6c\u79fb\u8fc7\u6765\uff0c\u5206\u522b\u662f\uff0c\u4e0a\u4e00\u6b21\u4f7f\u7528\u4e86\u673a\u4f1a\uff0c\u6216\u8005\u4e0a\u4e00\u6b21\u6ca1\u6709\u4f7f\u7528\u673a\u4f1a\uff0c\u6545\uff1a
\n$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
\n$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
\n\u5982\u679c\u5728\u8fd9\u4e2a\u70b9\u4f7f\u7528\u673a\u4f1a\u4e14\u6210\u529f\u7684\u8bdd\uff0c\u5219\u6709\uff1a
\n$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
\n$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
\n$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
\n\u7136\u540e\uff0c\u53ea\u9700\u8981\u8d70\u5230\u7ec8\u70b9\u5373\u53ef\uff0c\u56e0\u6b64:
\n$$ Ans=Min(f_{N,i,j})\\ (i\\in [0,M],j\\in [0,1])$$<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<cstring>\r\nusing namespace std;\r\n#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))\r\nint mp[305][305],N,M,V,E;\r\nint c[2005],d[2005];\r\ndouble p[2005],f[2005][2005][2];\r\nvoid init(){\r\n memset(mp,0x3f,sizeof(mp));\r\n scanf(\"%d%d%d%d\",&N,&M,&V,&E);\r\n for(int i=1;i<=N;++i){\r\n scanf(\"%d\",&c[i]);\r\n }\r\n for(int i=1;i<=N;++i){\r\n scanf(\"%d\",&d[i]);\r\n }\r\n for(int i=1;i<=N;++i){\r\n scanf(\"%lf\",&p[i]);\r\n }\r\n int u,v,w;\r\n for(int i=1;i<=E;++i){\r\n scanf(\"%d%d%d\",&u,&v,&w);\r\n mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);\r\n }\r\n for(int i=1;i<=V;++i){\r\n mp[i][i]=0;\r\n }\r\n for(int k=1;k<=V;++k){\r\n for(int i=1;i<=V;++i){\r\n for(int j=1;j<=V;++j){\r\n mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); \r\n }\r\n }\r\n }\r\n for(int i=1;i<=N;++i){\r\n for(int j=0;j<=M;++j){\r\n for(int k=0;k<=1;++k){\r\n f[i][j][k]=1000007;\r\n }\r\n }\r\n }\r\n f[1][0][0]=f[1][1][1]=0;\r\n for(int i=2;i<=N;++i){\r\n for(int j=0;j<=M;++j){\r\n f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));\r\n if(!j){\r\n continue;\r\n }\r\n f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));\r\n }\r\n }\r\n double ans=1000007;\r\n for(int i=0;i<=M;++i){\r\n for(int j=0;j<2;++j){\r\n ans=Min(ans,f[N][i][j]);\r\n }\r\n }\r\n \/*\r\n for(int i=1;i<=N;++i){\r\n for(int j=0;j<=M;++j){\r\n for(int k=0;k<2;++k){\r\n printf(\"%.2lf \",f[i][j][k]);\r\n }\r\n printf(\"|\");\r\n }\r\n puts(\"\");\r\n }\r\n *\/\r\n printf(\"%.2lf\",ans);\r\n}\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u4f18\\(d\\acute{u}\\)\u79c0\\(li\\acute{u}\\)\u7684\u671f\u671bDP\u3002 \u7b80\u8ff0\u9898\u610f\uff1a \u539f\u6709\u4e00\u4e2a\u5305\u62ec\\(n … <\/p>\n