\u5f00\u59cb\u5b66\u4e60\u671f\u671bDP\u3002
\n\u8fd9\u662f\u4e00\u9053\u671f\u671bDP\u5165\u95e8\u9898\u3002
\n\u9996\u5148\u6211\u4eec\u8bbe\\(f[i]\\)\u8868\u793a\uff0c\u5df2\u7ecf\u53d6\u4e86\\(i\\)\u79cd\u6570\uff0c\u8ddd\u79bb\u53d6\u5b8c\u7684\u671f\u671b\u56de\u5408\u6570\u3002
\n\u6839\u636e\u6982\u7387\u7684\u57fa\u672c\u5b9a\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u77e5\u9053\uff0c\u5df2\u7ecf\u53d6\u4e86\\(k\\)\u79cd\u4ee5\u540e\uff0c\u4e0b\u4e00\u79cd\u53d6\u5230\u7684\u662f\u672a\u53d6\u5230\u8fc7\u7684\u6982\u7387\u662f\\(\\frac{n-k}{n} \\)\uff1b\u800c\u53d6\u5230\u7684\u662f\u53d6\u8fc7\u7684\u6982\u7387\u662f\\(\\frac{k}{n}\\)
\n\u6211\u4eec\u5f88\u5bb9\u6613\u53ef\u4ee5\u77e5\u9053\uff0c\u5df2\u7ecf\u53d6\u4e86\\(i\\)\u79cd\u6570\uff0c\u4e0b\u4e00\u6b21\u53d6\u53ef\u80fd\u6709\u4e24\u79cd\u60c5\u51b5\uff1a
\n\u4e00\uff1a\u53d6\u5230\u7684\u662f\u4e00\u79cd\u65b0\u7684\u6570\u3002
\n\u4e8c\uff1a\u53d6\u5230\u7684\u662f\u5df2\u7ecf\u53d6\u5230\u8fc7\u7684\u6570\u3002
\n\u4f46\u65e0\u8bba\u5982\u4f55\u90fd\u8981\u518d\u53d6\u4e00\u6b21\u624d\u6709\u9020\u6210\u72b6\u6001\u6539\u53d8\u7684\u7a7a\u95f4\u3002
\n\u6545\u800c\u6211\u4eec\u5f97\u5230\u65b9\u7a0b\uff1a
\n$$ f_{i}=\\frac{n-i}{n}*f_{i+1}+\\frac{i}{n}*f_{i}+1 $$
\n\u5373\uff1a
\n$$ n*f_{i}=(n-i)*f_{i+1}+i*f_{i}+n $$
\n\u4ece\u800c\u5f97\u5230\uff1a
\n$$ f_{i}=\\frac{(n-i)*f_{i+1}+n}{n-i} $$
\n\u7b49\u4ef7\u4e8e\uff1a
\n$$ f_{i}=f_{i+1}+\\frac{n}{n-i} $$
\n\u4e8e\u662f\u6211\u4eec\u5f97\u5230\u4e86\u9006\u5411\u7684\u9012\u63a8\u65b9\u7a0b\u3002
\n\u7136\u540e\u662f\u8fb9\u754c\u6761\u4ef6\u3002\u5f88\u663e\u7136\uff0c\\(f_{n}=0\\)\uff0c\u8fd9\u662f\u56e0\u4e3a\uff0c\u5df2\u7ecf\u53d6\u5230\\(n\\)\u79cd\u4ee5\u540e\uff0c\u5c31\u610f\u5473\u7740\u5df2\u7ecf\u53d6\u5b8c\u4e86\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\nusing namespace std;\r\ndouble f[1005];\r\nint n;\r\nvoid init(){\r\n scanf(\"%d\",&n);\r\n f[n]=0;\r\n for(int i=n-1;i>=0;--i){\r\n f[i]=f[i+1]+(double)n\/(n-i);\r\n }\r\n printf(\"%.2lf\\n\",f[0]);\r\n}\r\nint main(){\r\n int T;\r\n scanf(\"%d\",&T);\r\n while(T--){\r\n init();\r\n }\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5f00\u59cb\u5b66\u4e60\u671f\u671bDP\u3002 \u8fd9\u662f\u4e00\u9053\u671f\u671bDP\u5165\u95e8\u9898\u3002 \u9996\u5148\u6211\u4eec\u8bbe\\(f[i]\\)\u8868\u793a\uff0c\u5df2\u7ecf\u53d6\u4e86\\(i\\)\u79cd\u6570\uff0c\u8ddd\u79bb\u53d6\u5b8c … <\/p>\n