A
树形dp是看起来比较靠谱的做法 , 但是转移的时候不全面就会出错 , 从贪心的角度出发 , 首先让第一量车走最长路,
然后就会发现递归结构 , 得到递归式 f[i] = ( f[i-2] + f[i-3] + .. + f[1]) * 2 + 1;
贪心的正确性 , 可以根据dp方程证出来 , 不过还是蛮显然的...
#define maxn 1000100
#define mod 1000000007
#define INF (1ll<<60)
llong dp[maxn][];
class TrafficCongestion {
public:
int theMinCars(int);
}; llong dfs(int h,int s)
{
int i,j;
llong resa,resb,resc;
dp[][] = ;
dp[][] = ;
dp[][] = ;
for ( i= ; i<=h ; i++ )
for ( j= ; j< ; j++ )
{
resa = resb =resc = INF;
if (j==)
{
resa = dp[i-][] + dp[i-][] + 1ll; resa %= mod;
resb = dp[i-][] + dp[i-][]; resb %= mod;
resc = dp[i-][] + dp[i-][]; resc %= mod;
}
else if (j==)
{
resa = dp[i-][] * 2LL % mod;
resb = dp[i-][] + dp[i-][]; resb %= mod;
}
else if (j==)
{
resa = dp[i-][] + dp[i-][]; resa %= mod;
resb = dp[i-][]*2LL + 1LL; resb %= mod;
}
resa = min(resa,resb);
resa = min(resa,resc);
dp[i][j] = resa;
}
return dp[h][s];
}
int TrafficCongestion::theMinCars(int h)
{
memset(dp,-,sizeof(dp));
llong ans = dfs(h,);
return ans;
}
B
假设每个value只有一个 , 那么只要构造递增次数为K的序列就行了 , 构造方法可以是:先取前k个作为k个递增序列的起点 ,
剩下的就是n-k个元素分配给,k个集合求方案数 , 但是这样无法保证每个序列递增 ,不过还是给我们一个启示:按递增顺序考虑.
定义dp[i][j] 为 前i个元素 , 已经构造了j个递增序列的方案数.
dp[i+1][j] = dp[i][j] * j + dp[i][j-1]
拓展到每个value可能出现多个的情况时 ,转移要乘上组合数.
using namespace std;
#define maxn 1300
typedef long long llong;
const llong mod = ;
class LISNumber {
public:
int count(vector <int>, int);
};
llong dp[][maxn],c[maxn][maxn];
int n,sum[maxn];
int LISNumber::count(vector <int> card, int K)
{
int i,j,k;
n = card.size();
for ( i= ; i<n ; i++ ) sum[i] = i? sum[i-]+card[i] : card[i]; for ( i=,c[][]= ; i<maxn ; i++ )
for ( j= ; j<=i ; j++ )
{
c[i][j] = j?c[i-][j-]+c[i-][j] : ;
c[i][j] %= mod;
} memset(dp,,sizeof(dp));
dp[][] = ;
for ( i= ; i<n ; i++ )
for ( j= ; j<=sum[i] && j<=K ; j++ ) if (dp[i][j])
{
// printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);
for ( k= ; k<=j && k<=card[i] ; k++ )
{
llong pos,add,x;
add = card[i]-k;
pos = ( (i?sum[i-]:) + ) - j + k;
x = c[j][k] * c[pos+add-][pos-] %mod * dp[i][j] % mod;
// printf("add to dp[%d][%d] ,k=%d: %lld\n",i+1,(int)(j+add),k,x);
dp[i+][j+add] += x;
dp[i+][j+add] %= mod;
}
}
// for ( i=0 ; i<=n ; i++ )
// for ( j=0 ; j<=K ; j++ ) if (dp[i][j]) printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);
return dp[n][K] % mod;
}
C
(计算几何不会 , 看题解撸了好久..)
判断点是否在三角形内部或边界:
顺时针地考虑每条边e , 如果黑点在e下方 , 则在内部 , 否则在外部 , 用叉积判断 , 注意叉积为0的时候 ,是恰好在边界上,应判为在内部;
统计方案数:
为了不重复统计 , 3元组(a,b,c)应该为升序 .
于是有了朴素的办法: 枚举三元组.
然后考虑: 对于确定的a , b有一个取值范围来保证 e(a,b) 这条边合法 , c也有一个取值范围来保证 e(c,a) 这条边合法 ,
用f(i)来表示对于点i , 能取的编号最大的点 , 很显然f(i)是递增的 , 然后根据单调性 , 利用"部分和"的技巧 , 可以o(n)统计方案数.
#define maxn (58585*4+100)
class EnclosingTriangle {
public:
long long getNumber(int, vector <int>, vector <int>);
}; struct node {
llong x,y;
};node e[maxn];
int t,f[maxn]; llong xmult(llong x0,llong y0,llong x1,llong y1) {
return x0*y1 - x1*y0;
} llong sum , add[maxn] , addid[maxn] , front , tail , c; int check(int A,int B,vector<int>x,vector<int> y) {
node a = e[A];
node b = e[B%t];
for (int i= ; i<(int)x.size() ; i++ ) {
if (xmult(a.x-x[i],a.y-y[i],b.x-x[i],b.y-y[i])>) return ;
}
return ;
} void sub(llong d) {
sum -= (tail-front) * d;
// printf("sub: cnt=%lld cut:%lld sum:%lld\n",tail-front,(tail-front)*d,sum);
while (front<tail && add[front]-c<) {
sum -= add[front]-c;
// printf("cut:%lld count:%lld otq:%lld\n",add[front]-c,add[front],addid[front]);
front++;
}
} void ins(int b) {
add[tail] = min(f[b]+,t);
addid[tail] = b;
sum += add[tail++]-c;
} long long EnclosingTriangle::getNumber(int m, vector <int> x, vector <int> y) {
for (int i= ; i< ; i++ ) {
for (int j= ; j<m ; j++ ) {
llong ox[] = {,j,m,m-j};
llong oy[] = {j,m,m-j,};
e[t++] = (node){ox[i],oy[i]};
}
}
for (int i=,j= ; i<t ; i++ ) {
while (check(i,j,x,y)) j++;
j--;
f[i] = j;
// printf ("f[%d]=%d\n",i,j);
}
c = ;
llong res = ;
for (int a=,b= ; a<t ; a++ ) {
llong d = ; while (front<tail && addid[front]<=a) {
sum -= add[front]-c;
// printf("front:%lld tail:%lld cut:%lld sum:%lld\n",front,tail,add[front]-c,sum);
front++;
}
while (f[c]<a+t && c+<t) c++,d++;
if (f[c]<a+t) break;
sub(d);
// printf("before add :sum:%lld c:%lld\n",sum,c);
while (b<=f[a]) {
if (min(f[b]+,t)-c>=) {
ins(b);
if (b==c) res--;
}
b++;
}
res += sum;
// printf("after add: sum:%lld c:%lld b:%d res:%lld\n",sum,c,b,res);
}
return res;
}