#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;
Category: DP
11040
#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]+
10911
#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
10359
#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
10918
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 3×1 for(int i=2;i<35;i++) { f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2×1) OR one vertical 2×1(and removing that will leave one missing cornered ractngle of 2
1099
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;
10874
#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; }
10898
#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
10337
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
11450
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) {