#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <queue> #include <cstdlib> #define INF 1000000000 #define ll long long using namespace std; int n,k; int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2 int periodOfCity[11][11]; ll dp[1010][15];//ll dp[day][citypath]; int kase=1; int costFromTheCity(int day,int startCity,int destination_city) { int schedulePeriod = periodOfCity[startCity][destination_city];
Category: DP
1645
#include <iostream> #include <cstdio> #define ll long long using namespace std; ll dp[1010]; int main() { int n,kase=1; dp[1]=1; for(int i=2;i<1001;i++) { for(int j=1;j<i;j++) { if((i-1)%j==0) { dp[i]+=dp[j]; dp[i]%=1000000007; } } } while(scanf("%d",&n)!=EOF) { cout<<"Case "<<kase++<<": "<<dp[n]<<"\n"; } return 0; }
473
This solution is based on 0/1 knapsack problem. dp[i][j][k] is the maximum amount of songs with i songs while k unit time is left in disk j. #include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <string> using namespace std; int N,T,M; int song[800]; int dp[800][100][100]; void DP() { for(int i=0;i<N;i++) { for(int j=0;j<=M;j++) {
10943
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; ll dp[105][105];//length,sum int N,K; void DP() { memset(dp,0,sizeof(dp)); for(int i=0;i<105;i++) dp[1][i]=1; for(int length = 2;length<=K;length++) { dp[length][0]=1; for(int sum=1;sum<=N;sum++) { for(int j=0;j<=sum;j++) { dp[length][sum]+=dp[length-1][sum-j]; dp[length][sum]%=1000000; } } } } int main() { while(scanf("%d%d",&N,&K),N+K) { DP(); cout<<dp[K][N]<<"\n"; } return 0; }
10616
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int N,Q; int M,D; int num[210]; int tt; int dp[210][15][25]; void DP() { dp[0][0][0]=1; for(int i=1;i<=N;i++) { for(int j=0;j<=M;j++) { for(int k=0;k<D;k++) { dp[i][j][k]=dp[i-1][j][k];//as no element is added if(j) { int tmp = (D+k-num[i]%D)%D;//in case k-num[i]%10 is less than 0 , D is added dp[i][j][k]+=dp[i-1][j-1][tmp]; //from
10721
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; ll dp[55][55]; int main() { int n,k,m; while(~scanf("%d%d%d",&k,&m,&n)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n && i<=k;i++) dp[1][i]=1; for(int i=2;i<=m;i++) { for(int j=i;j<=k;j++) { for(int l=1;l<=j && l<=n;l++) { dp[i][j]+=dp[i-1][j-l]; } } } cout<<dp[m][k]<<"\n"; } return 0; }
166
#include <iostream> #include <cstdio> #include <cstdlib> #include <iomanip> #include <fstream> #define INF 10000000 using namespace std; int availabe_coin[6]; int min_ways[1005]; int visit[6]; int coins[6]={5,10,20,50,100,200}; int cost; int cmp; void dp(int tcost,int index,int noOfsteps) { int tmp,v; if(tcost>=cost) { int d = tcost-cost; if(d>1003) return; if(min_ways[d]!=INF) { tmp = noOfsteps+min_ways[tcost-cost]; if(tmp<cmp) { cmp = tmp; return;
10912
#include <iostream> using namespace std; int L,S; int dp[27][352][27];//[length][total][last element] int res_dp[27][352]; int main() { int kase=1; for(int i=1;i<27;i++) { dp[1][i][i]=1; } for(int i=2;i<=26;i++)//length of the string for(int j=1;j<=351;j++)//sum of all the value for(int k=1;k<=26;k++)//max last ending value for(int ll=1;ll<k;ll++) { dp[i][j][k]+=dp[i-1][j-k][ll]; } for(int i=1;i<=26;i++) for(int j=1;j<=351;j++) for(int k=1;k<=26;k++) res_dp[i][j]+=dp[i][j][k]; while(cin>>L) { cin>>S; if(L+S==0) break;
116
#include <iostream> #include <cstdio> #define MX 100000000 using namespace std; int r,c; int input[11][101]; int dp[11][101]; int next_row[11][101]; int main() { int tmp,temp_position,row; while(scanf("%d%d",&r,&c)==2) { for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin>>input[i][j]; for(int i=0;i<r;i++) dp[i][c-1]=input[i][c-1]; for(int i=c-2;i>=0;i–) { for(int j=0;j<r;j++) { tmp=MX; for(int k=-1;k<=1;k++) { temp_position = (j+k+r)%r; if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i])) { next_row[j][i]=temp_position; tmp =
10910
Top Down: #include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 #define ll long long using namespace std; ll res[75][75]; int N,T,P; ll dp(int cnt,int rem) { if(cnt==1 || rem==0) return 1; if(res[cnt][rem]!=-1) return res[cnt][rem]; ll r =0; for(int i=0;i<=rem;i++) { r+= dp(cnt-1,rem-i); } res[cnt][rem]=r; return res[cnt][rem]; } int main() { int t;