*Combinatorial - Coin Changing Problem http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A 金額を払うのに必要な最小コイン枚数をDPで解く問題。 #include<stdio.h> #include<vector> int main(){ int n,m,memo[50001]={0}; scanf("%d %d",&n,&m); int coin; for(int i=0;i<m;i++){ scanf("%d",&coin); for(int j=0;j+coin<=n;j++){ if(memo[j]==0&&j>0)continue; if(memo[j+coin]==0||memo[j+coin]>memo[j]+1){ memo[j+coin]=memo[j]+1; } } } printf("%d\n",memo[n]); } *Combinatorial - 0-1 Knapsack Problem http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B 重さ付きナップザック問題。 #include<stdio.h> #include<vector> int main(){ int n,W,memo[10001]={0}; scanf("%d %d",&n,&W); int v,w,sum=0,ans=0; while(n--){ scanf("%d %d",&v,&w); if(sum+w>W)sum=W-w; for(int j=sum;j>=0;j--){ if(memo[j+w]<memo[j]+v)memo[j+w]=memo[j]+v; } sum+=w; } for(int i=0;i<=W;i++)if(ans<memo[i])ans=memo[i]; printf("%d\n",ans); } *Combinatorial - Longest Increasing Subsequence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D 数列の中の最長増加部分列の長さをこたえる問題。 ちょっと邪道な解法かも。 #include<stdio.h> #include<map> std::map<int,int> memo; i nt main(){ int n,a; std::map<int,int>::reverse_iterator rIt; scanf("%d",&n); memo[0]=-1; while(n--){ scanf("%d",&a); for(rIt=memo.rbegin();rIt!=memo.rend();rIt++){ if((*rIt).second<a){ memo[(*rIt).first+1]=a; break; } } if(memo.find(1)==memo.end() || memo[1]>a){ memo[1]=a; } } rIt=memo.rbegin(); printf("%d\n",(*rIt).first); }