とりあえず
また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); } }