DP – Page 2 – Live with passion

11002

Asif NaeemDecember 22, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

bool dp[65][65][6005];
int arr[65][65];
int n;

void init()
{
	for(int i=0;i<65;i++)
		for(int j=0;j<65;j++)
		{
			arr[i][j]=0;
			for(int k=0;k<6005;k++)
				dp[i][j][k]=0;
		}
}


int main()
{
	int cnt,tmp,tmp2,val;
	while(scanf("%d",&n),n)
	{
		init();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
				scanf("%d",&arr[i][j]);
		}
		cnt = n;
		for(int i=n+1;i<=2*n-1;i++)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				scanf("%d",&arr[i][j]);
			}
		}
		cnt = 0;
		dp[2*n-1][1][ arr[2*n-1][1]+3000 ] = 1;
		for(int i=2*n-1;i>=n+1;i--)
		{
			cnt+=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j];
						val = k+tmp;
						dp[i-1][j][val]=true;
						val = k-tmp;
						dp[i-1][j][val]=true;
						tmp2 = arr[i-1][j+1];
						val = k+tmp2;
						dp[i-1][j+1][val]=true;
						val = k-tmp2;
						dp[i-1][j+1][val]=true;
					}
				}
			}
		}// end of for loop
		cnt=n+1;
		for(int i=n;i>=2;i--)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j-1];
						tmp2 = arr[i-1][j];
						if(j==1)
						{
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
						else if(j==cnt)
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
						}
						else
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
					}
				}
			}
		}//end for loop
		int mn = 7000;
		for(int i=3000;i>=0;i--)
		{
			if(dp[1][1][i]==true)
			{
				mn=3000-i;
				break;
			}
		}
		int mx = 7000;
		for(int i=3001;i<6005;i++)
		{
			if(dp[1][1][i]==true)
			{
				mx=i-3000;
				break;
			}
		}
		cout<<(mn<mx?mn:mx)<<"\n";
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

using namespace std;

bool dp[65][65][6005];

int arr[65][65];

int n;

void init()

{

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

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

{

arr[i][j]=0;

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

dp[i][j][k]=0;

}

int main()

{

int cnt,tmp,tmp2,val;

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

{

init();

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

{

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

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

}

cnt = n;

for(int i=n+1;i<=2*n-1;i++)

{

cnt-=1;

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

{

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

}

cnt = 0;

dp[2*n-1][1][ arr[2*n-1][1]+3000 ] = 1;

for(int i=2*n-1;i>=n+1;i--)

{

cnt+=1;

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

{

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

{

if(dp[i][j][k]==true)

{

tmp = arr[i-1][j];

val = k+tmp;

dp[i-1][j][val]=true;

val = k-tmp;

dp[i-1][j][val]=true;

tmp2 = arr[i-1][j+1];

val = k+tmp2;

dp[i-1][j+1][val]=true;

val = k-tmp2;

dp[i-1][j+1][val]=true;

}

}// end of for loop

cnt=n+1;

for(int i=n;i>=2;i--)

{

cnt-=1;

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

{

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

{

if(dp[i][j][k]==true)

{

tmp = arr[i-1][j-1];

tmp2 = arr[i-1][j];

if(j==1)

{

val = k+tmp2;

dp[i-1][j][val]=true;

val = k-tmp2;

dp[i-1][j][val]=true;

}

else if(j==cnt)

{

val = k+tmp;

dp[i-1][j-1][val]=true;

val = k-tmp;

dp[i-1][j-1][val]=true;

}

else

{

val = k+tmp;

dp[i-1][j-1][val]=true;

val = k-tmp;

dp[i-1][j-1][val]=true;

val = k+tmp2;

dp[i-1][j][val]=true;

val = k-tmp2;

dp[i-1][j][val]=true;

}

}//end for loop

int mn = 7000;

for(int i=3000;i>=0;i--)

{

if(dp[1][1][i]==true)

{

mn=3000-i;

break;

}

int mx = 7000;

for(int i=3001;i<6005;i++)

{

if(dp[1][1][i]==true)

{

mx=i-3000;

break;

}

cout<<(mn<mx?mn:mx)<<"\n";

}

return 0;

}

11040

Asif NaeemDecember 21, 2015

#include <iostream>
#include <cstdio>

using namespace std;

int arr[10][10];

void init()
{
	for(int i=1;i<10;i++)
	{
		for(int j=1;j<10;j++)
			arr[i][j]=0;
	}
}
int main()
{
	int t,cnt,tmp;
	scanf("%d",&t);
	while(t--)
	{
		cnt=1;
		init();
		for(int i=9;i>=1;i-=2)
		{
			for(int j=1;j<=cnt;j+=2)
			{
				scanf("%d",&arr[i][j]);
			}
			cnt+=2;
		}
		cnt=7;
		for(int i=3;i<=9;i+=2)
		{
			for(int j=1;j<=cnt;j+=2)
			{
				tmp = arr[i][j];
				arr[i-2][j+1] = (tmp - (arr[i-2][j]+ arr[i-2][j+2]))/2;
			}
			for(int j=1;j<=cnt+1;j++)
			{
				arr[i-1][j]=arr[i-2][j]+arr[i-2][j+1];
			}
			cnt-=2;
		}
		cnt=1;
		for(int i=9;i>=1;i--)
		{
			for(int j=1;j<=cnt;j++)
			{
				printf("%d",arr[i][j]);
				cout<<(j!=cnt?" ":"\n");
			}
			cnt+=1;
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int arr[10][10];

void init()

{

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

{

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

arr[i][j]=0;

}

int main()

{

int t,cnt,tmp;

scanf("%d",&t);

while(t--)

{

cnt=1;

init();

for(int i=9;i>=1;i-=2)

{

for(int j=1;j<=cnt;j+=2)

{

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

}

cnt+=2;

}

cnt=7;

for(int i=3;i<=9;i+=2)

{

for(int j=1;j<=cnt;j+=2)

{

tmp = arr[i][j];

arr[i-2][j+1] = (tmp - (arr[i-2][j]+ arr[i-2][j+2]))/2;

}

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

{

arr[i-1][j]=arr[i-2][j]+arr[i-2][j+1];

}

cnt-=2;

}

cnt=1;

for(int i=9;i>=1;i--)

{

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

{

printf("%d",arr[i][j]);

cout<<(j!=cnt?" ":"\n");

}

cnt+=1;

}

return 0;

}

10911

Asif NaeemDecember 21, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;
struct HOUSE{
	double x,y;
};
string str[20];
HOUSE house[20];
double dp[(1<<16)-1];
double d[20][20];
int finalstate;
int n;

double _min(double a,double b)
{
	return a<b?a:b;
}
double DP(int state)
{
	if(state==finalstate)
	return 0;
	if(dp[state]!=-1)
		return dp[state];
	int rest_state = finalstate-state;
	double val=(1<<20);
	for(int i=0;i<2*n;i++)
	{
		if(rest_state&(1<<i))
		{
			for(int j=i+1;j<2*n;j++)
			{
				if(rest_state&(1<<j))
				{
					val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) ));
				}
			}
		}
	}
	return dp[state]=val;
}
int main()
{
	int kase=1;
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<(1<<2*n);i++)
			dp[i]=-1;
		finalstate=(1<<2*n)-1;
		for(int i=0;i<20;i++)
			for(int j=0;j<20;j++)
				d[i][j]=0;
		for(int i=0;i<2*n;i++)
		{
			cin>>str[i];
			scanf("%lf%lf",&house[i].x,&house[i].y);
		}
		for(int i=0;i<2*n-1;i++)
		{
			for(int j=i+1;j<2*n;j++)
			{
				d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) );
				d[j][i] = d[i][j];
			}
		}
		printf("Case %d: %.2lf\n",kase++,DP(0));
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

using namespace std;

struct HOUSE{

double x,y;

};

string str[20];

HOUSE house[20];

double dp[(1<<16)-1];

double d[20][20];

int finalstate;

int n;

double _min(double a,double b)

{

return a<b?a:b;

}

double DP(int state)

{

if(state==finalstate)

return 0;

if(dp[state]!=-1)

return dp[state];

int rest_state = finalstate-state;

double val=(1<<20);

for(int i=0;i<2*n;i++)

{

if(rest_state&(1<<i))

{

for(int j=i+1;j<2*n;j++)

{

if(rest_state&(1<<j))

{

val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) ));

}

return dp[state]=val;

}

int main()

{

int kase=1;

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

{

for(int i=0;i<(1<<2*n);i++)

dp[i]=-1;

finalstate=(1<<2*n)-1;

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

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

d[i][j]=0;

for(int i=0;i<2*n;i++)

{

cin>>str[i];

scanf("%lf%lf",&house[i].x,&house[i].y);

}

for(int i=0;i<2*n-1;i++)

{

for(int j=i+1;j<2*n;j++)

{

d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) );

d[j][i] = d[i][j];

}

printf("Case %d: %.2lf\n",kase++,DP(0));

}

return 0;

}

10359

Asif NaeemDecember 20, 2015

#include <iostream>
#include <cstdio>

using namespace std;

int f[260][1000];
int length[260];
void init()
{
	for(int i=0;i<260;i++)
	{
		length[i]=0;
		for(int j=0;j<1000;j++)
			f[i][j]=0;
	}
}
int main()
{
	int n,j,cary,begn;
	init();
	f[0][0]=1;
	f[1][0]=1;
	for(int i=2;i<260;i++)
	{
		cary=0;
		for(j=0;j<1000;j++)
		{
			f[i][j]=(f[i-1][j]+2*f[i-2][j]+cary)%10;
			cary=(f[i-1][j]+2*f[i-2][j]+cary)/10;
		}
		if(cary!=0)
		f[i][j]=cary;
	}
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=999;i>=0;i--)
		{
			if(f[n][i])
			{
				begn=i;
				break;
			}
		}
		for(int i=begn;i>=0;i--)
			printf("%d",f[n][i]);
		printf("\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int f[260][1000];

int length[260];

void init()

{

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

{

length[i]=0;

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

f[i][j]=0;

}

int main()

{

int n,j,cary,begn;

init();

f[0][0]=1;

f[1][0]=1;

for(int i=2;i<260;i++)

{

cary=0;

for(j=0;j<1000;j++)

{

f[i][j]=(f[i-1][j]+2*f[i-2][j]+cary)%10;

cary=(f[i-1][j]+2*f[i-2][j]+cary)/10;

}

if(cary!=0)

f[i][j]=cary;

}

while(scanf("%d",&n)!=EOF)

{

for(int i=999;i>=0;i--)

{

if(f[n][i])

{

begn=i;

break;

}

for(int i=begn;i>=0;i--)

printf("%d",f[n][i]);

printf("\n");

}

return 0;

}

10918

Asif NaeemDecember 20, 2015

Using DP

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int f[35];
int g[35];

int main()
{
	for(int i=0;i<35;i++)
		f[i]=g[i]=0;
	f[0]=1;
	f[1]=0;
	g[0]=0;
	g[1]=1;//one missing cornered rect of size 3x1
	for(int i=2;i<35;i++)
	{
		f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways)
		g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",f[n]);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int f[35];

int g[35];

int main()

{

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

f[i]=g[i]=0;

f[0]=1;

f[1]=0;

g[0]=0;

g[1]=1;//one missing cornered rect of size 3x1

for(int i=2;i<35;i++)

{

f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways)

g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle

}

int n;

while(scanf("%d",&n) && n!=-1)

{

printf("%d\n",f[n]);

}

return 0;

}

Another way of adhoc suggested in a blog.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int arr[35];

//lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be
// tiled 3 ways ,so total ways for n length is ways[n-2]*3
//if n>=4 then for every term it can be shifted upside down adds two more ways
// so for n>=4
int main()
{
	for(int i=0;i<35;i++)
		arr[i]=0;
	arr[0]=1;

	for(int i=2;i<35;i+=2)
	{
		arr[i]+=3*arr[i-2];
		for(int j=4;j<=i;j+=2)
		{
			arr[i] += 2*arr[i-j];
		}
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",arr[n]);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int arr[35];

//lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be

// tiled 3 ways ,so total ways for n length is ways[n-2]*3

//if n>=4 then for every term it can be shifted upside down adds two more ways

// so for n>=4

int main()

{

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

arr[i]=0;

arr[0]=1;

for(int i=2;i<35;i+=2)

{

arr[i]+=3*arr[i-2];

for(int j=4;j<=i;j+=2)

{

arr[i] += 2*arr[i-j];

}

int n;

while(scanf("%d",&n) && n!=-1)

{

printf("%d\n",arr[n]);

}

return 0;

}

1099

Asif NaeemDecember 8, 2015

DP+bitmask

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
//#include <fstream>
#include <cmath>

using namespace std;

int sizes[16];
int n;
int row,col;
int sum[32780];//1<<n-1=state
int dp[105][32780];//[width or height][state]

int _min(int a,int b)
{
	if(a<b)
	return a;
	return b;
}
//karnighan's bit count algorithm
int check(int x)
{
	int res=0;
	for(res=0;x>0;res++)
	{
		x=x&(x-1);
	}
	return res;
}
int DP(int len,int states)
{
	if(check(states)==1)
	{
		return dp[len][states]=1;
	}
	if(dp[len][states]!=-1)
		return dp[len][states];
	int ans=0,width;
	width = sum[states]/len;
	for(int i=states&(states-1);i>0;i=(i-1)&states)
	{
		int rest = states-i;//= states^i;
		if(sum[i]%len==0 && sum[rest]%len==0)
		{
			ans = DP( _min( len, sum[i]/len ) , i) + DP( _min( len, sum[rest]/len ) , rest);
			if(ans==2)
			return dp[len][states]=1;
		}
		if(sum[i]%width==0 && sum[rest]%width==0)
		{
			ans = DP( _min( width, sum[i]/width ), i) + DP( _min( width, sum[rest]/width ), rest);//states^i == is the state indicates who are not deliverd at state i
			if(ans==2)
			return dp[len][states]=1;
		}
	}
	return dp[len][states]=0;
}

int main()
{
	int tmp,total;
	int kase=1;
	//ofstream out;
	//out.open("my_out.txt");
	while(scanf("%d",&n),n)
	{
		scanf("%d%d",&row,&col);
		total=0;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&sizes[i]);
			total+=sizes[i];
		}
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<32780;j++)
				dp[i][j] = -1;
		}
		for(int i=0;i<(1<<n);i++)
		{
			total = 0;
			for(int j=0;j<n;j++)
			{
				tmp = 1<<j;
				if(i & tmp)
				total += sizes[j];
			}
			sum[i]=total;
		}
		if(sum[(1<<n)-1]!=row*col)
		{
			printf("Case %d: No\n",kase);
			//out<<"Case "<<kase<<": No\n";
			kase+=1;
			continue;
		}
		int f = DP(_min(row,col),(1<<n)-1);//final row and where all the chocklets are accumulated
		if(f==1)
		{
			printf("Case %d: Yes\n",kase);
			kase+=1;
		}
		else
		{
			//out<<"Case "<<kase<<": No\n";
			printf("Case %d: No\n",kase);
			kase+=1;
		}
	}
	//out.close();
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

//#include <fstream>

#include <cmath>

using namespace std;

int sizes[16];

int n;

int row,col;

int sum[32780];//1<<n-1=state

int dp[105][32780];//[width or height][state]

int _min(int a,int b)

{

if(a<b)

return a;

return b;

}

//karnighan's bit count algorithm

int check(int x)

{

int res=0;

for(res=0;x>0;res++)

{

x=x&(x-1);

}

return res;

}

int DP(int len,int states)

{

if(check(states)==1)

{

return dp[len][states]=1;

}

if(dp[len][states]!=-1)

return dp[len][states];

int ans=0,width;

width = sum[states]/len;

for(int i=states&(states-1);i>0;i=(i-1)&states)

{

int rest = states-i;//= states^i;

if(sum[i]%len==0 && sum[rest]%len==0)

{

ans = DP( _min( len, sum[i]/len ) , i) + DP( _min( len, sum[rest]/len ) , rest);

if(ans==2)

return dp[len][states]=1;

}

if(sum[i]%width==0 && sum[rest]%width==0)

{

ans = DP( _min( width, sum[i]/width ), i) + DP( _min( width, sum[rest]/width ), rest);//states^i == is the state indicates who are not deliverd at state i

if(ans==2)

return dp[len][states]=1;

}

return dp[len][states]=0;

}

int main()

{

int tmp,total;

int kase=1;

//ofstream out;

//out.open("my_out.txt");

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

{

scanf("%d%d",&row,&col);

total=0;

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

{

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

total+=sizes[i];

}

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

{

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

dp[i][j] = -1;

}

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

{

total = 0;

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

{

tmp = 1<<j;

if(i & tmp)

total += sizes[j];

}

sum[i]=total;

}

if(sum[(1<<n)-1]!=row*col)

{

printf("Case %d: No\n",kase);

//out<<"Case "<<kase<<": No\n";

kase+=1;

continue;

}

int f = DP(_min(row,col),(1<<n)-1);//final row and where all the chocklets are accumulated

if(f==1)

{

printf("Case %d: Yes\n",kase);

kase+=1;

}

else

{

//out<<"Case "<<kase<<": No\n";

printf("Case %d: No\n",kase);

kase+=1;

}

//out.close();

return 0;

}

10874

Asif NaeemDecember 3, 2015

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

#define ll long long
#define INF 500000000

using namespace std;

struct point{
	int left;
	int right;
};
point arr[20005];
ll dp[20005][2];

void init()
{
	for(int i=0;i<20005;i++)
		for(int j=0;j<2;j++)
			dp[i][j]=INF;
}

ll _min(ll a,ll b)
{
	if(a<b)
	return a;
	return b;
}
int main()
{
	int n;
	ll path;
	int y1,y2;
	while(scanf("%d",&n),n)
	{
		init();
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&y1,&y2);
			arr[i].left=(y1<=y2?y1:y2);
			arr[i].right=(y1>=y2?y1:y2);
		}
		dp[1][0]=_min(dp[1][0], (arr[1].right-1) + (arr[1].right-arr[1].left) );
		dp[1][1]=_min(dp[1][1], (arr[1].right-1) );

		for(int i=2;i<=n;i++)
		{
			dp[i][0] = _min( dp[i][0] , _min( dp[i-1][0] + (arr[i].right - arr[i].left) + abs(arr[i].right-arr[i-1].left),
											  dp[i-1][1] + (arr[i].right - arr[i].left) + abs(arr[i].right-arr[i-1].right) ) )+1;
			dp[i][1] = _min( dp[i][1] , _min( dp[i-1][0] + (arr[i].right - arr[i].left) + abs(arr[i].left-arr[i-1].left),
											  dp[i-1][1] + (arr[i].right - arr[i].left) + abs(arr[i].left-arr[i-1].right)  ) )+1;
		}
		path = ( (dp[n][0]+n-arr[n].left) < (dp[n][1]+n-arr[n].right)? (dp[n][0]+n-arr[n].left):(dp[n][1]+n-arr[n].right));
		printf("%lld\n",path);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

#define ll long long

#define INF 500000000

using namespace std;

struct point{

int left;

int right;

};

point arr[20005];

ll dp[20005][2];

void init()

{

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

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

dp[i][j]=INF;

}

ll _min(ll a,ll b)

{

if(a<b)

return a;

return b;

}

int main()

{

int n;

ll path;

int y1,y2;

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

{

init();

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

{

scanf("%d%d",&y1,&y2);

arr[i].left=(y1<=y2?y1:y2);

arr[i].right=(y1>=y2?y1:y2);

}

dp[1][0]=_min(dp[1][0], (arr[1].right-1) + (arr[1].right-arr[1].left) );

dp[1][1]=_min(dp[1][1], (arr[1].right-1) );

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

{

dp[i][0] = _min( dp[i][0] , _min( dp[i-1][0] + (arr[i].right - arr[i].left) + abs(arr[i].right-arr[i-1].left),

dp[i-1][1] + (arr[i].right - arr[i].left) + abs(arr[i].right-arr[i-1].right) ) )+1;

dp[i][1] = _min( dp[i][1] , _min( dp[i-1][0] + (arr[i].right - arr[i].left) + abs(arr[i].left-arr[i-1].left),

dp[i-1][1] + (arr[i].right - arr[i].left) + abs(arr[i].left-arr[i-1].right) ) )+1;

}

path = ( (dp[n][0]+n-arr[n].left) < (dp[n][1]+n-arr[n].right)? (dp[n][0]+n-arr[n].left):(dp[n][1]+n-arr[n].right));

printf("%lld\n",path);

}

return 0;

}

10898

Asif NaeemDecember 2, 2015

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

#define INF 100000000
#define ll long long

using namespace std;

int MX,cnt;
int Item,Combo,noOfOrder;
ll bestDp[1000000];
ll packPrice[1000000];
int packages[20];

void init()
{
	cnt=0;
	for(int i=0;i<1000000;i++)
	{
		bestDp[i]=INF;
		packPrice[i]=0;
	}
	for(int i=0;i<20;i++)
		packages[i]=0;
}

ll _min(ll a,ll b)
{
	if(a<b)
	return a;
	return b;
}
int isContain(int order,int packs)
{
	if(packs>order)
		return 0;
	while(order>0 && packs>0)
	{
		if(order%10 < packs%10)
			return 0;
		order/=10;
		packs/=10;
	}
	return 1;
}

int _pow(int a,int p)
{
	if(p==0)
		return 1;
	else
		return (_pow(a,p-1)*a);
}

void DP()
{
	for(int order=1;order<1000000;order++)
	{
		for(int i=0;i<cnt;i++)
		{
			if(isContain(order,packages[i]))
			{
				bestDp[order]=_min(bestDp[order],bestDp[order-packages[i]] + packPrice[packages[i]] );
			}
		}
	}
}
int main()
{
	int a,idx,multiplier,val;
	int Orders;
	while(scanf("%d",&Item)!=EOF)
	{
		init();
		for(int i=0;i<Item;i++)
		{
			idx = _pow(10,i);
			scanf("%lld",&packPrice[idx]);
			bestDp[idx]=packPrice[idx];
			packages[cnt]=idx;
			cnt+=1;
		}
		scanf("%d",&Combo);
		for(int i=0;i<Combo;i++)
		{
			 idx=0;
			 for(int j=0;j<Item;j++)
			{
				scanf("%d",&a);
				multiplier=_pow(10,j);
				a=a*multiplier;
				idx+=a;
			}
			scanf("%lld",&packPrice[idx]);
			packages[cnt]=idx;
			bestDp[idx]=_min(bestDp[idx],packPrice[idx]);
			cnt+=1;
		}
		scanf("%d",&noOfOrder);
		DP();
		for(int II=0;II<noOfOrder;II++)
		{
			val = 0;
			for(int JJ=0;JJ<Item;JJ++)
			{
				scanf("%d",&a);
				multiplier=_pow(10,JJ);
				a=a*multiplier;
				val+=a;
			}
			Orders=val;
			printf("%lld\n",bestDp[Orders]);
		}
	 }
	 return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <iostream>

#include <cstdio>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

#define INF 100000000

#define ll long long

using namespace std;

int MX,cnt;

int Item,Combo,noOfOrder;

ll bestDp[1000000];

ll packPrice[1000000];

int packages[20];

void init()

{

cnt=0;

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

{

bestDp[i]=INF;

packPrice[i]=0;

}

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

packages[i]=0;

}

ll _min(ll a,ll b)

{

if(a<b)

return a;

return b;

}

int isContain(int order,int packs)

{

if(packs>order)

return 0;

while(order>0 && packs>0)

{

if(order%10 < packs%10)

return 0;

order/=10;

packs/=10;

}

return 1;

}

int _pow(int a,int p)

{

if(p==0)

return 1;

else

return (_pow(a,p-1)*a);

}

void DP()

{

for(int order=1;order<1000000;order++)

{

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

{

if(isContain(order,packages[i]))

{

bestDp[order]=_min(bestDp[order],bestDp[order-packages[i]] + packPrice[packages[i]] );

}

int main()

{

int a,idx,multiplier,val;

int Orders;

while(scanf("%d",&Item)!=EOF)

{

init();

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

{

idx = _pow(10,i);

scanf("%lld",&packPrice[idx]);

bestDp[idx]=packPrice[idx];

packages[cnt]=idx;

cnt+=1;

}

scanf("%d",&Combo);

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

{

idx=0;

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

{

scanf("%d",&a);

multiplier=_pow(10,j);

a=a*multiplier;

idx+=a;

}

scanf("%lld",&packPrice[idx]);

packages[cnt]=idx;

bestDp[idx]=_min(bestDp[idx],packPrice[idx]);

cnt+=1;

}

scanf("%d",&noOfOrder);

DP();

for(int II=0;II<noOfOrder;II++)

{

val = 0;

for(int JJ=0;JJ<Item;JJ++)

{

scanf("%d",&a);

multiplier=_pow(10,JJ);

a=a*multiplier;

val+=a;

}

Orders=val;

printf("%lld\n",bestDp[Orders]);

}

return 0;

}

10337

Asif NaeemNovember 30, 2015

It’s a bottom up dp approach.

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>

#define INF 100000000

using namespace std;
vector<int> vb[11];
vector<int> v;
int dp[11][1010];

void init()
{
	for(int i=0;i<11;i++)
	{
		vb[i].clear();
		for(int j=0;j<1010;j++)
		{
			dp[i][j]=-1;
		}
	}
}

int _min(int a,int b,int c,int d)
{
	v.clear();
	v.push_back(a);
	v.push_back(b);
	v.push_back(c);
	v.push_back(d);
	sort(v.begin(),v.end());
	return v[0];
}

int mn(int a,int b,int c)
{
	v.clear();
	v.push_back(a);
	v.push_back(b);
	v.push_back(c);
	sort(v.begin(),v.end());
	return v[0];
}
int main()
{
	int t,X,slot,a,b,c,d;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&X);
		init();
		slot = X/100;
		for(int i=9;i>=0;i--)
		{
			for(int j=0;j<slot;j++)
			{
				scanf("%d",&a);
				vb[i].push_back(a);
			}
		}
		dp[0][1]=30-vb[0][0];
		dp[1][1]=60-vb[0][0];
		for(int i=2;i<=slot;i++)
		{
			for(int j=0;j<=9;j++)
			{
				if(j>0 && j<9)
				{
					if(dp[j-1][i-1]==-1)a = INF;
					else a = dp[j-1][i-1]+60-vb[j-1][i-1];

					if(dp[j][i-1]==-1)b = INF;
					else b = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j+1][i-1]==-1)c = INF;
					else c = dp[j+1][i-1]+20-vb[j+1][i-1];

					if(dp[j][i]==-1)d = INF;
					else d = dp[j][i];
					dp[j][i]=_min(a,b,c,d);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );
				}
				else if(j==9)
				{
					if(dp[j-1][i-1]==-1)a = INF;
					else a = dp[j-1][i-1]+60-vb[j-1][i-1];

					if(dp[j][i-1]==-1)b = INF;
					else b = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j][i]==-1)c = INF;
					else c = dp[j][i];
					dp[j][i]=mn(a,b,c);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1] );
				}
				else if(j==0)
				{
					if(dp[j][i-1]==-1)a = INF;
					else a = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j+1][i-1]==-1)b = INF;
					else b = dp[j+1][i-1]+20-vb[j+1][i-1];

					if(dp[j][i]==-1)c = INF;
					else c = dp[j][i];

					dp[j][i]=mn(a,b,c);//_min( dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );
				}
			}
		}
		cout<<dp[0][slot]<<"\n\n";
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <iostream>

#include <cstdio>

#include <queue>

#include <sstream>

#include <string>

#include <queue>

#include <vector>

#include <cstring>

#include <algorithm>

#include <cmath>

#define INF 100000000

using namespace std;

vector<int> vb[11];

vector<int> v;

int dp[11][1010];

void init()

{

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

{

vb[i].clear();

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

{

dp[i][j]=-1;

}

int _min(int a,int b,int c,int d)

{

v.clear();

v.push_back(a);

v.push_back(b);

v.push_back(c);

v.push_back(d);

sort(v.begin(),v.end());

return v[0];

}

int mn(int a,int b,int c)

{

v.clear();

v.push_back(a);

v.push_back(b);

v.push_back(c);

sort(v.begin(),v.end());

return v[0];

}

int main()

{

int t,X,slot,a,b,c,d;

scanf("%d",&t);

while(t--)

{

scanf("%d",&X);

init();

slot = X/100;

for(int i=9;i>=0;i--)

{

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

{

scanf("%d",&a);

vb[i].push_back(a);

}

dp[0][1]=30-vb[0][0];

dp[1][1]=60-vb[0][0];

for(int i=2;i<=slot;i++)

{

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

{

if(j>0 && j<9)

{

if(dp[j-1][i-1]==-1)a = INF;

else a = dp[j-1][i-1]+60-vb[j-1][i-1];

if(dp[j][i-1]==-1)b = INF;

else b = dp[j][i-1]+30-vb[j][i-1];

if(dp[j+1][i-1]==-1)c = INF;

else c = dp[j+1][i-1]+20-vb[j+1][i-1];

if(dp[j][i]==-1)d = INF;

else d = dp[j][i];

dp[j][i]=_min(a,b,c,d);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );

}

else if(j==9)

{

if(dp[j-1][i-1]==-1)a = INF;

else a = dp[j-1][i-1]+60-vb[j-1][i-1];

if(dp[j][i-1]==-1)b = INF;

else b = dp[j][i-1]+30-vb[j][i-1];

if(dp[j][i]==-1)c = INF;

else c = dp[j][i];

dp[j][i]=mn(a,b,c);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1] );

}

else if(j==0)

{

if(dp[j][i-1]==-1)a = INF;

else a = dp[j][i-1]+30-vb[j][i-1];

if(dp[j+1][i-1]==-1)b = INF;

else b = dp[j+1][i-1]+20-vb[j+1][i-1];

if(dp[j][i]==-1)c = INF;

else c = dp[j][i];

dp[j][i]=mn(a,b,c);//_min( dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );

}

cout<<dp[0][slot]<<"\n\n";

}

return 0;

}

11450

Asif NaeemNovember 30, 2015

It’s a bottom up approach.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>

#define INF 100000000
using namespace std;

int MX;
vector<int> vb[21];
int dp[201][21];

void init()
{
	for(int i=0;i<21;i++)
	vb[i].clear();
	MX = INF;
	for(int i=0;i<201;i++)
		for(int j=0;j<21;j++)
		{
			if(j==0)
			dp[i][j]=0;
			else
			dp[i][j]=-1;//not solved
		}
}

int _max(int a,int b)
{
	if(a>b)
	return a;
	return b;
}
int main()
{
	int t,K,a;
	int M,C;
	scanf("%d",&t);
	while(t--)
	{
		init();
		scanf("%d%d",&M,&C);
		for(int i=1;i<=C;i++)
		{
			scanf("%d",&K);
			for(int j=0;j<K;j++)
			{
				scanf("%d",&a);
				vb[i].push_back(a);
			}
		}//for ends
		for(int i=1;i<=C;i++)
		{
			for(int j=0;j<vb[i].size();j++)
			{
				int val = vb[i][j];
				for(int k=0;k<=M;k++)
				{
					if(val<=k && dp[k-val][i-1]!=-1)
					dp[k][i]=_max(dp[k-val][i-1]+val,dp[k][i]);
				}
			}
		}
		if(dp[M][C]==-1)
		printf("no solution\n");
		else
		{
			printf("%d\n",dp[M][C]);
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <vector>

#define INF 100000000

using namespace std;

int MX;

vector<int> vb[21];

int dp[201][21];

void init()

{

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

vb[i].clear();

MX = INF;

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

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

{

if(j==0)

dp[i][j]=0;

else

dp[i][j]=-1;//not solved

}

int _max(int a,int b)

{

if(a>b)

return a;

return b;

}

int main()

{

int t,K,a;

int M,C;

scanf("%d",&t);

while(t--)

{

init();

scanf("%d%d",&M,&C);

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

{

scanf("%d",&K);

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

{

scanf("%d",&a);

vb[i].push_back(a);

}

}//for ends

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

{

for(int j=0;j<vb[i].size();j++)

{

int val = vb[i][j];

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

{

if(val<=k && dp[k-val][i-1]!=-1)

dp[k][i]=_max(dp[k-val][i-1]+val,dp[k][i]);

}

if(dp[M][C]==-1)

printf("no solution\n");

else

{

printf("%d\n",dp[M][C]);

}

return 0;

}

Category: DP

11002

11040

10911

10359

10918

1099

10874

10898

10337

11450

Archives

Categories