for(int k=0;k
f1=false;
if(xmul(i,m,m,j,x[k],y[k])>0)
f2=false;
}
upleft[i][j]=f1;upright[i][j]=f2;
}
}
for(int i=1;i
for(int k=0;k
f1=false;
if(xmul(i,0,m,j,x[k],y[k])<0)
f2=false;
}
downleft[i][j]=f1;downright[i][j]=f2;
}
}
for(int i=1;i
for(int k=0;k
f1=false;
if(xmul(i,m,j,0,x[k],y[k])>0)
f2=false;
}
updown_toright[i][j]=f1;updown_toleft[i][j]=f2;
}
}
for(int i=1;i
for(int k=0;k
f1=false;
if(xmul(0,i,m,j,x[k],y[k])>0)
f2=false;
}
leftright_toup[i][j]=f1;leftright_todown[i][j]=f2;
}
}
int ans=0;
for(int i=1;i
// cout<
}
}
}
for(int i=1;i
// cout<
}
}
}
for(int i=1;i
// cout<
}
}
}
for(int i=1;i
// cout<
}
}
}
return ans;
}
};
DIV1 250 PT TrafficCongestion
一棵满二叉树，问有多少条不相交的路径，遍历所有的点
观察奇偶的最优解，得到递推式，两个奇的合成偶的，无法合并原来的路径，还得单独考虑根，所以是两倍加1
两个偶的，有一条路径可以合并，所以是两倍减1
比赛的时候。。。没考虑到0的情况。。。23333
[cpp]
int dp[1000005];
class TrafficCongestion {
public:
int theMinCars(int treeHeight) {
dp[0]=1;
for(int i=1;i<=treeHeight;i++)
if(i&1) dp[i]=(dp[i-1]*2-1)%MOD;
else dp[i]=(dp[i-1]*2+1)%MOD;
return dp[treeHeight];
}
};
int dp[1000005];
class TrafficCongestion {
public:
int theMinCars(int treeHeight) {
dp[0]=1;
for(int i=1;i<=treeHeight;i++)
if(i&1) dp[i]=(dp[i-1]*2-1)%MOD;
else dp[i]=(dp[i-1]*2+1)%MOD;
return dp[treeHeight];
}
};
DIV1 500PT LISNumber
从大到小插入到序列当中，dp[i][j]表示考虑了i种数，目前LISnumber为j的数目。
那么考虑i-1的时候，有cnt[i-1]个这样的数。
如果新增了k个lisnumber。那么剩下的cnt[i-1]-k个数插入进去是没有产生lisnumber的。
只要插入点在原来的lis起点的前面，才不会新增。
也就是在原来的j个lis前面选出cnt[i-1]-k个位置，插入这些数，不产生lisnumber。
剩下的k个数，插入是要新增lisnumber的。位置包括之前的那cnt[i-1]-k个位置，序列的末端以及每个lis的中间sum-t。
这一部分转化为k个相同的物品放入到cnt[i-1]-k+1+sum-t个不同的容器中的方案数，DP解决。
[cpp]
const int MOD = 1000000007;
LL c[40*40][40*40];
LL dp[40][1300];
LL a[40*40][40];
class LISNumber {
public:
LL PowMod(LL a,LL b){
LL ret=1;
while(b){
if(b&1) ret=((LL)ret*a)%MOD;
a=((LL)a*a)%MOD;
b>>=1;
}
return ret;
}
int count(vector
int n=cardsnum.size();
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
for(int i=1;i<=36*36;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j
}
a[0][0]=1LL;
for(int i=0;i<=37*37;i++){
for(int j=0;j<=37;j++){
for(int k=0;k<=37&&j+k<=37;k++){
a[i+1][j+k]=(a[i+1][j+k]+a[i][j])%MOD;
}