程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5089 使做對k-1題最大概率的選題方案

hdu 5089 使做對k-1題最大概率的選題方案

編輯：C++入門知識

hdu 5089 使做對k-1題最大概率的選題方案

給出N道難度遞增的題目，難度用可能做出的百分比表示，選出K道題目使得做出K-1道題目的概率最大。
選k題的情況下做出k-1的概率為所有(1-p)*p*p...的和，直接嘗試轉化這個式子的效果並不明顯。
換個思路，假設最優解已經包含了k-1個了，現在來選取最後一個。K-1個全部做出的概率是Pall(k−1)，有一道為做出的概率是Pless(k−1)，現在選取的是PCk，那麼做出K-1道的概率是
Pall(k−1)∗(1−P[PCk])+Pless(k−1)∗P[PCk]=
Pall(k−1)+P[PCk]∗(Pless(k−1)−Pall(k−1))
這是一個關於PCk的一次函數，如果Pless(k−1)−Pall(k−1)為正，選取最大的PCk，否則選取最小的。

那麼我們每次選取的時候一定是選擇剩下的最大或最小，那麼說明答案一定是選取兩邊的概率，枚舉比較一下就可以算出最大的概率了。
但是要求的是字典序最小的。左邊不用管，對於右邊，如果存在相同的value，應該選取index較小的。然後隨便搞下就ok了。

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define RD(x) scanf(%d,&x)
#define RD2(x,y) scanf(%d%d,&x,&y)
#define RD3(x,y,z) scanf(%d%d%d,&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
#define eps 1e-9
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const int modo = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int inf = 0x3fffffff;
const LL _inf = 1e18;
const int maxn = 55,maxm = 1<<12;
int n,k;
bool vis[maxn];
double p[maxn];
int pos[maxn],s[maxn];
int main()
{
    int _,_g;RD(_);
    while(_--){
        RD2(n,k);
        clr0(vis);
        for(int i = 0;i < n;++i){
            RD(s[i]);
            p[i] = ((double)s[i])/100.0;
        }
        double mx = 0;
        for(int g = 0;g <= k;++g){//選擇前g個和後k - g個
            double _p,res = 0;
            int cnt = 0;
            for(int i = 0;i < g;++i)
                pos[cnt++] = i;
            for(int i = 1;i <= k - g;++i)
                pos[cnt++] = n - i;
            for(int i = 0;i < cnt;++i){
                _p = 1;
                for(int j = 0;j < cnt;++j){
                    if(j != i)
                        _p *= p[pos[j]];
                    else
                        _p *= (1 - p[pos[j]]);
                }
                res += _p;
            }
            if(mx - res < eps){
                mx = res;
                _g = g;
            }
        }
        for(int i = 0;i < _g;++i)
            vis[i] = 1;
        for(int i = n - (k - _g);i < n;++i){
            for(int j = i;j >= 0;--j){
                if(vis[j] || s[j] > s[i])
                    break;
                _g = j;
            }
            vis[_g] = 1;
        }
        _g = 1;
        for(int i = 0;i < n;++i)
            if(vis[i])
                printf(%d%c,i+1, 
[_g == k]),_g++;
    }
    return 0;
}