[2018 겨울방학 캠프데이2] [다이내믹 플랜] 울타리 수리

2970 단어 문제풀이동적 기획
울타리 수리 문제 설명: 샤오즈가 최근에 농장주가 되었다!그러나 축하를 하기도 전에 까다로운 문제 하나가 작은 z 앞에 놓여 있었다.농장의 울타리는 오랫동안 수리를 하지 않아 여러 군데가 파손되었다.울타리는 n개의 널빤지로 구성되어 있으며, 모든 널빤지는 이미 손상되었을 수도 있고 손상되지 않았을 수도 있다.작은 z는 연속 m개의 널빤지(이 m개의 널빤지가 모두 파손된 것은 아니다)를 수리하는 비용이 sqrt(m)라는 것을 알고 있다.그러나 어떻게 방안을 설계해야만 총 비용을 가장 낮출 수 있습니까?샤오즈가 도와달라고 했어요.입력 형식: 입력 파일의 첫 번째 줄은 울타리의 길이를 나타내는 정수 n을 포함한다.두 번째 행에는 공백으로 분리된 정수(긴 정수) n개가 포함됩니다.만약 i번째 숫자가 0이라면 i번째 널빤지가 이미 파손되었음을 의미하며, 그렇지 않으면 파손되지 않았다는 것을 의미한다.출력 형식: 출력 파일에 실수만 포함되어 있으며 최소 수리 비용을 표시합니다.주의: 답안은 소수점 아래 세 자리까지 정확하다.데이터 규모: 30%의 데이터 중 n<=20.100% 데이터 중 n<=2500.입력 9 0 – 1 0 1 2 3 0 – 2 0 출력 3.000 [문제풀이 사고방식] 각 부서진 널빤지에 대해 우리가 생각해야 할 것은 앞에 있는 널빤지를 같이 고칠지, 아니면 따로 고칠지, 앞에 있는 널빤지 그룹을 같이 고칠지, 어느 널빤지로 널빤지 그룹을 시작하는지 봐야 하기 때문에 상태 이동 방정식을 쓸 수 있다.
f[i]=min(f[i],f[j]+sqrt(i-j));(0<=j<=i)

[참고 절차]
#include
#include
#include
#include
using namespace std;
int n,a[2501];
double f[2501];
int main()
{
    freopen("fence.in","r",stdin);
    freopen("fence.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    f[0]=0;
    for (int i=1;i<=n;i++)
    {
        f[i]=0xfff;
        if (a[i]!=0) f[i]=f[i-1];
        for (int j=0;jsqrt(i-j));
    }
    cout<3)<return 0;
}
파일 수정 불가 - GITLABCE
레이저 가공용 G-code를 만들어 봤어요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage