読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

とりあえず

またDP一問埋め +貪欲一個

3616

最初はdp[i]:=i分までの最大値としていましたがこれではTLE。
ちょっと負け組になってきましたがdp[i]:=i番目の区間を使った時の最大値で通りました。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct inter {
    int s, e, ef;
    bool operator<(const inter& a)const{
        return s<a.s;
    }
};
int n,m,r,s,e,ef;
int dp[1000];
inter list[1000];
int main() {
    memset(dp, 0, sizeof(dp));
    scanf("%d%d%d",&n,&m,&r);
    for (int i=0; i<m; i++) {
        scanf("%d%d%d",&list[i].s,&list[i].e,&list[i].ef);
    }
    sort(list,list+m);
    int res=0;
    for (int i=0; i<m; i++) {
        for (int j=0; j<i; j++) {
            if (list[i].s>=list[j].e+r) dp[i]=max(dp[i],dp[j]);
        }
        dp[i]+=list[i].ef;
        res=max(res,dp[i]);
    }
    printf("%d\n",res);
}

1017

結局考え方はあってるんだけど実装してるとちょこちょこミスっちゃうから他人の表現に力を借りてしまった。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a,b,c,d,e,f;
int main() {
    while (scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f)) {
        if (!a&&!b&&!c&&!d&&!e&&!f) break;
        int s1=0, s2=0;
        f+=e; f+=d;
        s1+=e*11; s2+=d*5;
        switch (c%4) {
            case 0: s1+=0; s2+=0; break;
            case 1: s1+=7; s2+=5; break;
            case 2: s1+=6; s2+=3; break;
            case 3: s1+=5; s2+=1; break;
        }
        f+=(c+3)/4;
        if (s2>=b) {
            s1+=(s2-b)*4;
            b=0;
        } else {
            b-=s2;
        }
        f+=(b+8)/9;
        s1+=(9-b%9)%9*4;
        a-=min(s1,a);
        f+=(a+35)/36;
        printf("%d\n",f);
    }
}
広告を非表示にする