#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
Category: Algorithm
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
10363
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int xwin[8]; int owin[8]; /* 1 XX. XX. OOO */ string str[4]; bool rowcheck(char c) { for(int i=0;i<3;i++) { if(str[i][0]==str[i][1] && str[i][0]==str[i][2] && str[i][0]==c) return 1; } return 0; } bool diagncheck(char c) { if(str[0][0]==str[1][1] && str[1][1]==str[2][2] && str[1][1]==c) return 1; if(str[0][2]==str[1][1] && str[1][1]==str[2][0] && str[1][1]==c)
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
10849
two positions of a NxN chess board can be connected by pawns move(diagonally) iff both of them are on black/white position, this can be checked by checking the pair. if both of the x,y (start position ) and X,Y(end position) are odd,odd or even,even then they can be connected or both of the pair are
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) {
11122
It took me long time to get accepted. Needs some geometric knowledge, used graham scan algorithm, can be done also without using that, but most importantly made me crazy to figure out the special cases. So the coding was not well formatted. Adding some special input cases for the problem. #include <iostream> #include <cstdio> #include