DP – Page 3 – Live with passion

590

Asif NaeemOctober 21, 2015

#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];
	int dayOfschedule = day%(schedulePeriod);
	if(dayOfschedule==0)
		dayOfschedule=schedulePeriod;
	return flight_schedule_cost[startCity][destination_city][dayOfschedule];
}
ll DP(int day,int city)
{
	ll d;
	int cost;
	dp[1][1]=0;
	for(int i=1;i<=n;i++)
		dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]);
	for(int i=3;i<=(k+1);i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int kk=1;kk<=n;kk++)
			{
				if(j==kk)
					continue;
				if(dp[i-1][kk]==INF)
					continue;
				cost = costFromTheCity(i-1,kk,j);
				if(cost==0)
					continue;
				dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]);
			}
		}
	}
	return dp[k+1][n];
}
int main()
{
	int dailyCost;

	while(scanf("%d%d",&n,&k),n+k)
	{
		memset(flight_schedule_cost,0,sizeof(flight_schedule_cost));
		memset(periodOfCity,0,sizeof(periodOfCity));
		memset(dp,INF,sizeof(dp));
		for(int i=0;i<1010;i++)
			for(int j=0;j<15;j++)
				dp[i][j]=INF;
		for(int start_city=1;start_city<=n;start_city++)
		{
			for(int destination_city=1;destination_city<=n;destination_city++)
			{
				if(destination_city==start_city)
				continue;
				scanf("%d",&periodOfCity[start_city][destination_city]);
				for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++)
				{
					scanf("%d",&dailyCost);
					flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost;
				}
			}
		}
		ll tmp = DP(k+1,n);
		if(tmp!=INF)
		{
			printf("Scenario #%d\n",kase++);
			printf("The best flight costs %lld.\n\n",tmp);
		}
		else
		{
			printf("Scenario #%d\n",kase++);
			printf("No flight possible.\n\n");
		}
	}
	return 0;
}

#include <iostream>

#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];

int dayOfschedule = day%(schedulePeriod);

if(dayOfschedule==0)

dayOfschedule=schedulePeriod;

return flight_schedule_cost[startCity][destination_city][dayOfschedule];

}

ll DP(int day,int city)

{

ll d;

int cost;

dp[1][1]=0;

for(int i=1;i<=n;i++)

dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]);

for(int i=3;i<=(k+1);i++)

{

for(int j=1;j<=n;j++)

{

for(int kk=1;kk<=n;kk++)

{

if(j==kk)

continue;

if(dp[i-1][kk]==INF)

continue;

cost = costFromTheCity(i-1,kk,j);

if(cost==0)

continue;

dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]);

}

return dp[k+1][n];

}

int main()

{

int dailyCost;

while(scanf("%d%d",&n,&k),n+k)

{

memset(flight_schedule_cost,0,sizeof(flight_schedule_cost));

memset(periodOfCity,0,sizeof(periodOfCity));

memset(dp,INF,sizeof(dp));

for(int i=0;i<1010;i++)

for(int j=0;j<15;j++)

dp[i][j]=INF;

for(int start_city=1;start_city<=n;start_city++)

{

for(int destination_city=1;destination_city<=n;destination_city++)

{

if(destination_city==start_city)

continue;

scanf("%d",&periodOfCity[start_city][destination_city]);

for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++)

{

scanf("%d",&dailyCost);

flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost;

}

ll tmp = DP(k+1,n);

if(tmp!=INF)

{

printf("Scenario #%d\n",kase++);

printf("The best flight costs %lld.\n\n",tmp);

}

else

{

printf("Scenario #%d\n",kase++);

printf("No flight possible.\n\n");

}

return 0;

}

1645

Asif NaeemMay 16, 2015

#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;
}

#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

Asif NaeemApril 8, 2015

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++)
		{
			for(int k=0;k<=T;k++)
			{
				if(k<song[i])
				dp[i+1][j][k]=dp[i][j][k];
				else if(k>=song[i])
				dp[i+1][j][k]=max(dp[i][j][k-song[i]]+1,dp[i][j][k]);
				if(j)
				dp[i+1][j][k]=max(dp[i][j-1][T-song[i]]+1,dp[i+1][j][k]);
			}
		}
	}
}

int main()
{
	int tt;
	cin>>tt;

	while(tt--)
	{
		cin>>N>>T>>M;
		cin>>song[0];
		for(int i=1;i<N;i++)
		{
			scanf(", %d",&song[i]);
		}
		memset(dp,0,sizeof(dp));
		DP();

		int res = 0;
		for(int i=0;i<=N;i++)
		{
			res = max(res,dp[i][M][0]);
		}
		cout<<res<<"\n";
		if(tt)
		cout<<"\n";
	}
	return 0;
}

#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++)

{

for(int k=0;k<=T;k++)

{

if(k<song[i])

dp[i+1][j][k]=dp[i][j][k];

else if(k>=song[i])

dp[i+1][j][k]=max(dp[i][j][k-song[i]]+1,dp[i][j][k]);

if(j)

dp[i+1][j][k]=max(dp[i][j-1][T-song[i]]+1,dp[i+1][j][k]);

}

int main()

{

int tt;

cin>>tt;

while(tt--)

{

cin>>N>>T>>M;

cin>>song[0];

for(int i=1;i<N;i++)

{

scanf(", %d",&song[i]);

}

memset(dp,0,sizeof(dp));

DP();

int res = 0;

for(int i=0;i<=N;i++)

{

res = max(res,dp[i][M][0]);

}

cout<<res<<"\n";

if(tt)

cout<<"\n";

}

return 0;

}

10943

Asif NaeemApril 7, 2015

#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;
}

#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

Asif NaeemApril 7, 2015

#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 i-1 elemnts j-1 elements selected where previous remainder was
					//tmp
				}
			}
		}
	}
}

int main()
{
	int kase=1,cnt=1;
	bool flag;
	while(scanf("%d%d",&N,&Q),N+Q)
	{
		for(int i=1;i<=N;i++)
			cin>>num[i];
		flag = 1;
		cnt = 1;
		for(int i=1;i<=Q;i++)
		{
			cin>>D>>M;
			memset(dp,0,sizeof(dp));
			DP();
			if(flag)
			{
				cout<<"SET "<<kase++<<":\n";
				flag = 0;
			}
			cout<<"QUERY "<<cnt++<<": ";
			cout<<dp[N][M][0]<<"\n";
		}


	}
	return 0;
}

#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 i-1 elemnts j-1 elements selected where previous remainder was

//tmp

}

int main()

{

int kase=1,cnt=1;

bool flag;

while(scanf("%d%d",&N,&Q),N+Q)

{

for(int i=1;i<=N;i++)

cin>>num[i];

flag = 1;

cnt = 1;

for(int i=1;i<=Q;i++)

{

cin>>D>>M;

memset(dp,0,sizeof(dp));

DP();

if(flag)

{

cout<<"SET "<<kase++<<":\n";

flag = 0;

}

cout<<"QUERY "<<cnt++<<": ";

cout<<dp[N][M][0]<<"\n";

}

return 0;

}

10721

Asif NaeemApril 6, 2015

#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;
}

#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

Asif NaeemMarch 31, 2015

#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;
			}
		}
	}
	for(int i=index+1;i<6;i++)
	{
		if(availabe_coin[i]==0)
		continue;
		if(visit[i]==0)
		{
			visit[i]=1;
			v = availabe_coin[i];
			for(int j=1;j<=v;j++)
			{
				availabe_coin[i]-=j;
				dp(tcost+j*coins[i],i,noOfsteps+j);
				availabe_coin[i]+=j;
			}
			visit[i]=0;
		}
	}
}

int main()
{
	int total,v,p,q;
	for(int i=0;i<1005;i++)
		min_ways[i]=INF;

	min_ways[0]=0;

	for(int i=0;i<6;i++)
	{
		for(int j=coins[i];j<1005;j++)
		{
			min_ways[j]= min(min_ways[j],1+min_ways[j-coins[i]]);
		}
	}
	while(scanf("%d",&availabe_coin[0]))
	{
		visit[0]=0;
		total = availabe_coin[0];
		for(int i=1;i<=5;i++)
		{
			scanf("%d",&availabe_coin[i]);
			visit[i]=0;
			total += availabe_coin[i];
		}
		if(total==0)
		break;

		scanf("%d.%d",&p,&q);
		cost=q+p*100;
		cmp = INF;
		for(int i=0;i<6;i++)
		{
			if(availabe_coin[i]==0)
			continue;
			if(visit[i]==0)
			{
				visit[i]=1;
				v = availabe_coin[i];
				for(int j=1;j<=v;j++)
				{
					availabe_coin[i]-=j;
					dp(0+j*coins[i],i,0+j);
					availabe_coin[i]+=j;
				}
				visit[i]=0;
			}
		}
		cout<<setw(3)<<cmp<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

#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;

}

for(int i=index+1;i<6;i++)

{

if(availabe_coin[i]==0)

continue;

if(visit[i]==0)

{

visit[i]=1;

v = availabe_coin[i];

for(int j=1;j<=v;j++)

{

availabe_coin[i]-=j;

dp(tcost+j*coins[i],i,noOfsteps+j);

availabe_coin[i]+=j;

}

visit[i]=0;

}

int main()

{

int total,v,p,q;

for(int i=0;i<1005;i++)

min_ways[i]=INF;

min_ways[0]=0;

for(int i=0;i<6;i++)

{

for(int j=coins[i];j<1005;j++)

{

min_ways[j]= min(min_ways[j],1+min_ways[j-coins[i]]);

}

while(scanf("%d",&availabe_coin[0]))

{

visit[0]=0;

total = availabe_coin[0];

for(int i=1;i<=5;i++)

{

scanf("%d",&availabe_coin[i]);

visit[i]=0;

total += availabe_coin[i];

}

if(total==0)

break;

scanf("%d.%d",&p,&q);

cost=q+p*100;

cmp = INF;

for(int i=0;i<6;i++)

{

if(availabe_coin[i]==0)

continue;

if(visit[i]==0)

{

visit[i]=1;

v = availabe_coin[i];

for(int j=1;j<=v;j++)

{

availabe_coin[i]-=j;

dp(0+j*coins[i],i,0+j);

availabe_coin[i]+=j;

}

visit[i]=0;

}

cout<<setw(3)<<cmp<<"\n";

}

return 0;

}

10912

Asif NaeemMarch 29, 2015

#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;

		cout<<"Case "<<kase++<<": ";
		if(L>0 && L<=26 && S>0 && S<=351)
			cout<<res_dp[L][S]<<"\n";
		else
			cout<<0<<"\n";
	}

	return 0;
}

#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;

cout<<"Case "<<kase++<<": ";

if(L>0 && L<=26 && S>0 && S<=351)

cout<<res_dp[L][S]<<"\n";

else

cout<<0<<"\n";

}

return 0;

}

116

Asif NaeemMarch 28, 2015

#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 = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}

#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 = dp[temp_position][i+1];

}

dp[j][i]=input[j][i]+tmp;

}

tmp = MX;

for(int i=0;i<r;i++)

{

if(tmp>dp[i][0])

{

tmp = dp[i][0];

row = i;

}

cout<<row+1;

for(int i=0;i<c-1;i++)

{

row = next_row[row][i];

cout<<" "<<row+1;

}

cout<<"\n"<<tmp<<"\n";

}

return 0;

}

#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 = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}

#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 = dp[temp_position][i+1];

}

dp[j][i]=input[j][i]+tmp;

}

tmp = MX;

for(int i=0;i<r;i++)

{

if(tmp>dp[i][0])

{

tmp = dp[i][0];

row = i;

}

cout<<row+1;

for(int i=0;i<c-1;i++)

{

row = next_row[row][i];

cout<<" "<<row+1;

}

cout<<"\n"<<tmp<<"\n";

}

return 0;

}

10910

Asif NaeemFebruary 1, 2015

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;
	cin>>t;

	while(t--)
	{
		cin>>N>>T>>P;
		for(int i=0;i<75;i++)
			for(int j=0;j<75;j++)
				res[i][j]=-1;
		cout<<dp(N,T-N*P)<<"\n";
	}

	return 0;
}

#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;

cin>>t;

while(t--)

{

cin>>N>>T>>P;

for(int i=0;i<75;i++)

for(int j=0;j<75;j++)

res[i][j]=-1;

cout<<dp(N,T-N*P)<<"\n";

}

return 0;

}

Category: DP

590

1645

473

10943

10616

10721

166

10912

116

10910

Archives

Categories