DP(ABC057D - Maximum Average Sets)

atcoder.jp

前回のやつより簡単だった（ただのナップサック問題で考察がほとんどいらないただのDPだったので）
何個選ぶか決めた時、価値の平均値が大きい順は価値の合計値が大きい順と同じ。合計を保持するDPを作って、最後にそれを個数で割って平均値を出し、そのうち個数がA個以上B個以下のもので一番価値の平均値が大きくなったものを出力すれば良い。
品物の選び方が何通りあるかは、別に配列を保持して数えれば良い。

DPに使う配列の初期化をミスって20分くらい使ったが、記事を書きながら40分くらいでできたので、コンテストで出たら良いなあ(明らかに前やったDPの方が2倍くらい難しいんだけど同じ点数なのか…)

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

int main(void){
    int N,A,B;
    scanf("%d %d %d",&N,&A,&B);
    long long int v[51];
    rep(i,N)scanf("%lld",&v[i]);
    long double ave=0;
    long long int cas=0;
    long long int dp[51][51];//dp[j][k]=j番目まででkこ使った時の合計値の最大値
    long long int dp_case[51][51];//同様に選び方の場合の数
    rep(j,N){
        if(j==0){
            dp[0][0]=0;dp[0][1]=v[0];
            dp_case[0][0]=1;dp_case[0][1]=1;
        }else rep(k,j+2){
            dp[j][k]=-1;dp_case[j][k]=-1;
            if(dp[j][k]<dp[j-1][k]){
                dp[j][k]=dp[j-1][k];
                dp_case[j][k]=dp_case[j-1][k];
            }else if(dp[j][k]==dp[j-1][k]){
                dp_case[j][k]+=dp_case[j-1][k];
            }
            if(k-1>-1)if(dp[j][k]<dp[j-1][k-1]+v[j]){
                dp[j][k]=dp[j-1][k-1]+v[j];
                dp_case[j][k]=dp_case[j-1][k-1];
            }else if(dp[j][k]==dp[j-1][k-1]+v[j]){
                dp_case[j][k]+=dp_case[j-1][k-1];
            }
            if(j==N-1&&k>=A&&k<=B&&dp_case[j][k]>0){
                long double newave=(long double)(dp[j][k])/(long double)(k);
                if(ave<newave){
                    ave=newave;cas=dp_case[N-1][k];
                }else if(ave==newave){
                    cas+=dp_case[N-1][k];
                }
            }
        }
    }
    printf("%llf\n%lld\n",ave,cas);
}