斎戒
DP斎戒
AOJ 2197
DPじゃないやん(バシッ
#include <cstdio> int cnt[1001]; int main() { int n; for (int i=1; i<=1000; i++) { int sum=i; for (int j=i+1;; j++) { sum+=j; if (sum>1000) break; cnt[sum]++; } } while (scanf("%d",&n)) { if (!n) break; printf("%d\n",cnt[n]); } }
PKU 1036
どうやら同時に複数人のgangが入れたらしい・・・
いろいろ最後の詰でいじめられた
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> using namespace std; int n, k, tl; int t[100], p[100], s[100]; int dp[2][101]; int main() { scanf("%d%d%d",&n,&k,&tl); for (int i=0; i<n; i++) scanf("%d",&t[i]); for (int i=0; i<n; i++) scanf("%d",&p[i]); for (int i=0; i<n; i++) scanf("%d",&s[i]); vector<vector<int> > gangs(tl+1); for (int i=0; i<n; i++) { if (gangs[t[i]].empty()) { gangs[t[i]]=vector<int>(k+1); } gangs[t[i]][s[i]]+=p[i]; } for (int i=0; i<2; i++) { for (int j=0; j<=k; j++) dp[i][j]=-99999; } dp[0][0]=0; for (int i=1; i<=tl; i++) { for (int j=0; j<=k; j++) { if (j-1>=0) dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-1]); dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j]); if (j+1<=k) dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j+1]); if (!gangs[i].empty()) dp[i&1][j]+=gangs[i][j]; } } int res=0; for (int i=0; i<=k; i++) res=max(res,dp[tl&1][i]); printf("%d\n",res); }
AOJ 0202
これはこれで計算量すくなくなるはずの実装でバグっていじめられた
#include <cstdio> #include <cstring> #include <algorithm> #define MAX 1000001 using namespace std; int n, x; int isprime[MAX]; int w[30]; int dp[MAX]; int main() { memset(isprime, 1, sizeof(isprime)); isprime[0]=isprime[1]=0; for (int i=2; i<MAX; i++) { if (isprime[i]) { for (int j=i*2; j<MAX; j+=i) isprime[j]=0; } } while (scanf("%d%d",&n,&x)) { if (n==0&&x==0) break; memset(dp, 0, sizeof(dp)); for (int i=0; i<n; i++) scanf("%d",&w[i]); dp[0]=1; for (int i=0; i<=x; i++) { if (dp[i]) { for (int j=0; j<n; j++) { if (i+w[j]<=x) dp[i+w[j]]=1; } } } int res=-1; for (int i=x; i>0; i--) { if (dp[i]&&isprime[i]) { res=i; break; } } if (res==-1) puts("NA"); else printf("%d\n",res); } }