首页 > 代码库 > 2014 HDU多校弟九场I题 不会DP也能水出来的简单DP题

2014 HDU多校弟九场I题 不会DP也能水出来的简单DP题

听了ZWK大大的思路,就立马1A了

思路是这样的:

算最小GPA的时候,首先每个科目分配到69分(不足的话直接输出GPA 2),然后FOR循环下来使REMAIN POINT减少,每个科目的上限加到100即可

算最大GPA的时候,首先每个科目分配到60分,然后FOR循环下来使REMAIN POINT减少,每个科目的上限加到85即可,如果还有REMAIN POINT,就FOR循环下来加到100上限即可

 

不会DP 阿 QAQ

过段时间得好好看DP了  =  =

于是默默的把这题标记为《水题集》

    //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler    #include <stdio.h>    #include <iostream>    #include <cstring>    #include <cmath>    #include <stack>    #include <queue>    #include <vector>    #include <algorithm>    #define ll long long    #define Max(a,b) (((a) > (b)) ? (a) : (b))    #define Min(a,b) (((a) < (b)) ? (a) : (b))    #define Abs(x) (((x) > 0) ? (x) : (-(x)))    #define NN 200011    using namespace std;    const ll INF = 0x3f3f3f3f;    const ll MAXN = 300001;    int main(){        int i, j, n, m, k;        int numCase;        int score, sum;        int a[11];        scanf("%d",&numCase);        while(numCase--){            double Gmax = 0.0;            double Gmin = 0.0;            scanf("%d%d",&score,&n);            sum = score * n;            if(score < 60)  Gmax = 2;            else{                for(i = 1; i <= n; ++i){                    a[i] = 60;                }                int remain = sum - n * 60;                while(remain != 0){                    for(i = 1; i <= n; ++i){                        if(a[i] <= 85){                            int delta = 85 - a[i];                            if(remain > delta){                                a[i] += delta;                                remain -= delta;                            } else{                                a[i] += remain;                                remain = 0;                                break;                            }                        }                    }                    for(i = 1; i <= n; ++i){                        if(a[i] <= 100){                            int delta = 100 - a[i];                            if(remain > delta){                                a[i] += delta;                                remain -= delta;                            } else{                                a[i] += remain;                                remain = 0;                                break;                            }                        }                    }                }                for(i = 1; i <= n; ++i){                    if(a[i] >= 85)  Gmax += 4.0;                    else if(a[i] >= 80) Gmax += 3.5;                    else if(a[i] >= 75) Gmax += 3.0;                    else if(a[i] >= 70) Gmax += 2.5;                    else if(a[i] >= 60) Gmax += 2.0;                }                Gmax /= n;            }            if(score < 69)  Gmin = 2;            else{                for(i = 1; i <= n; ++i){                    a[i] = 69;                }                int remain = sum - n * 69;                while(remain != 0){                    for(i = 1; i <= n; ++i){                        if(a[i] <= 100){                            int delta = 100 - a[i];                            if(remain > delta){                                a[i] += delta;                                remain -= delta;                            } else{                                a[i] += remain;                                remain = 0;                                break;                            }                        }                    }                }                for(i = 1; i <= n; ++i){                    if(a[i] >= 85)  Gmin += 4.0;                    else if(a[i] >= 80) Gmin += 3.5;                    else if(a[i] >= 75) Gmin += 3.0;                    else if(a[i] >= 70) Gmin += 2.5;                    else if(a[i] >= 60) Gmin += 2.0;                }                Gmin /= n;            }            printf("%.4f %.4f\n",Gmin,Gmax);        }        return 0;    }