uvalive4731

제목 대의: 숫자의 개수 n과 나누어야 할 조수 w를 제시한다.그리고 각 숫자의 확률을 제시하여 최소한의 수학적 기대를 구한다.
아이디어: DP.최소한의 수학적 기대를 요구하기 때문에 확률이 높은 것은 앞에 놓아야 하기 때문에 먼저 순서를 정해야 한다.dp[i][j]는 i조 전 j개의 숫자가 얻을 수 있는 가장 작은 수학적 기대를 나타낸다.
코드:

#include 
using namespace std;
#include 
#include 
#include 
const int INF = 0x3f3f3f3f;
const int maxn = 105;

int f[maxn][maxn];
int num[maxn],sum[maxn];
bool cmp(int a,int b) {
    return a > b;
}
int main() {

    int t;
    scanf("%d",&t);
    while(t--) {
        int n,w;
        scanf("%d %d",&n,&w);
        for(int i = 1; i <= n; i++)
            scanf("%d",&num[i]);
        sort(num + 1, num + 1 + n,cmp);

        sum[1] = num[1];
        for(int i = 2; i <= n ; i++)
            sum[i] = num[i] + sum[i - 1];

        for(int i = 1; i <= w; i++) {//  
            for(int j = i ; j <= i + n -w; j++) {//  j       <= i + n - w        w - i              ，  j   n - (w - i) i + n - w
                if(i == 1) {//            
                    f[i][j] = j * sum[j];
                    continue;
                }
                f[i][j] = INF;
                for(int k = i - 1; k < j ; k++) 
                    f[i][j] = min(f[i][j],f[i - 1][k] + j *(sum[j] - sum[k]));//            

            }
        }
        //printf("%d
",f[w][n]);
        double ans = f[w][n]/100.0;
        printf("%.4lf
",ans);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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