用dp做的,最后一组数据为什么过不了,我感觉好像没错,有大佬能教一下吗
查看原帖
用dp做的,最后一组数据为什么过不了,我感觉好像没错,有大佬能教一下吗
526409
new_a_girl楼主2022/4/1 16:41
#include<iostream>
using namespace std;
double d1, c, d2, p; int n,cnt;
double dp[10][10];
double a[10][2];
void dfs(int x) {
    if (x >= n + 2) { cnt = 1; return; }
    for (int i = n+2; i >x; i--) {
        if (a[i][0] - a[x][0] <= c * d2) { dfs(i); }
    }
}
int main() {
    cin >> d1 >> c >> d2 >> p >> n;
    a[1][0] = 0; a[1][1] = p;
    a[n + 2][0] = d1; a[n + 2][1] = 1;
    for (int i = 2; i <= n + 1; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    dfs(1);
    if (cnt != 1) { cout << "No Solution" << endl; return 0; }
    for (int i = 1; i <= n + 1; i++) {
        dp[i][i] = 10000;
        for (int j = i + 1; j <= n + 2; j++) {
            dp[i][j] = (a[j][0] - a[i][0]) / d2 * a[i][1];
        }
    }
    for (int i = n + 2; i >= 1; i--) {
        for (int j = i - 1; j >= 1; j--) {
            for (int k = n + 1;k > j ; k--) {
                dp[j][i] = min(dp[j][i], dp[j][k] + dp[k][n + 2]);
            }
        }
    }
    
    printf("%.2f", dp[1][n+2]);
    return 0;
}
2022/4/1 16:41
加载中...