dp第5点没过,大佬看看谢谢
查看原帖
dp第5点没过,大佬看看谢谢
362878
jerry090811楼主2022/2/8 17:48
#include <bits/stdc++.h>
using namespace std;
double f[11][1005];
int c[11][1005];
int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++){
        int x;
        double a1,b1,a2,b2;
        cin>>x>>a1>>b1>>a2>>b2;
        for (int j=0;j<a1*100;j++) c[x][j]=1;
        for (int j=(b1*100)+1;j<a2*100;j++) c[x][j]=1;
        for (int j=b2*100+1;j<=1000;j++) c[x][j]=1;
    }
    for (int i=0;i<=1000;i++){
        if (i!=500) c[0][i]=1;
    }
    for (int i=1;i<=10;i++){
        for(int j=0;j<=1000;j++){
            if (c[i][j]==0){
                double minx=100000;
                for (int k=0;k<=1000;k++){
                    if (c[i-1][k]==0) {
                        double l=k,m=j;
                        double dis=sqrt(1+((l-m)/100)*((l-m)/100))+f[i-1][k];
                        if (dis<minx) minx=dis;
                    }
                }
                f[i][j]=minx;
            }
        }
    }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<f[10][500];
    return 0;
}
2022/2/8 17:48
加载中...