此题与其类似，只不过把步数变成了战斗力。其实这个转换就像BFS中把无权图中的步数变成了有权图的最短路。BFS要搜索的东西变了，但是本质是一样的。
这里把步数变成战斗力，所以要把 dp 的状态转移变成战斗力的转移。
总之就是什么变就对什么构造状态转移方程。就像BFS中要找关于哪个变量的最短路就设置关于哪个变量的优先队列。
#include #include #include #include #include #include #include #include #include #pragma comment(linker, /STACK:1024000000); #define EPS (1e-8) #define LL long long #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) const double PI = acos(-1.0); using namespace std; int c[110]; double dp[10010]; int t[110]; int main() { int n,f; int i,j; while(scanf(%d %d,&n,&f) != EOF) { int Max = 0; for(i = 1; i <= n; ++i) { scanf(%d,&c[i]); t[i] = floor((1+sqrt(5.0))*c[i]*c[i]/2.0); Max = max(Max,c[i]); } for(dp[Max+1] = 0,i = 1; i <= n; ++i) { dp[Max+1] += t[i]; } dp[Max+1] /= n; for(i = Max; i >= f; --i) { dp[i] = 0; for(j = 1; j <= n; ++j) { if(i > c[j]) { dp[i] += t[j]; } else if(i+c[j] <= Max) { dp[i] = dp[i] + dp[i+c[j]] + 1; } else { dp[i] = dp[i] + dp[Max+1] + 1; } } dp[i] /= n; } printf(%.3lf ,dp[f]); } return 0; }