第一次看到这种骚东西， 期望还能二分的啊？？？
因为存在重置的操作， 所以我们再dp的过程中有环存在。
为了消除环的影响， 我们二分dp[ 0 ][ 0 ]的值， 与通过dp得出的dp[ 0 ][ 0 ]的值进行比较。
这样看着好像很不合理， 但实际上比较这两个值， 你能推倒出当前二分的值合不合法。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1000000007; const double eps = 1e-6; const double PI = acos(-1); int n, R, F[N], S[N], up; double P[N]; double dp[50 + 7][50 * 100 + 7]; double dfs(int i, int j, double x) { if(i == n) { if(j <= R) return 0; else return x; } if(dp[i][j] + eps > 0) return dp[i][j]; double T1 = P[i + 1] * (dfs(i + 1, j + F[i + 1], x) + F[i + 1]) + (1 - P[i + 1]) * (dfs(i + 1, j + S[i + 1], x) + S[i + 1]); dp[i][j] = min(T1, x); return dp[i][j]; } bool check(double x) { for(int i = 0; i <= n; i++) for(int j = 0; j <= up; j++) dp[i][j] = -1; if(dfs(0, 0, x) < x) return true; else return false; } int main() { scanf("%d%d", &n, &R); for(int i = 1; i <= n; i++) { scanf("%d%d%lf", &F[i], &S[i], &P[i]); P[i] /= 100; up += S[i]; } double low = n, high = 5e8; for(int o = 1; o <= 100; o++) { double mid = (low + high) / 2; if(check(mid)) high = mid; else low = mid; } printf("%.12f\n", (low + high) / 2); return 0; } /* */
