毒瘤出题人JR搞来了三道DP......
T1
jr的电脑密码
jr.cpp/.c/.pas
题目描述：
趁着jr出去吃饭，某人打算机惨jr，但他惊奇地发现，jr电脑居然有密码！每次给出两个正整数n，m，对于一个非空序列S，满足S中元素之和为n，且它们取模m互不相同，密码就是S的个数取模905229641。
注：两个序列不同当且仅当它们的顺序，长度，元素不同。如{0,1,2}，{1,0,2}是不同的。
输入(jr.in)：
两个正整数，n，m。
输出(jr.out)：
一个正整数，为密码。
jr0.in：
jr0.out：
3 3
9
样例解释：
合法序列为{3}，{0,1,2}，{1,2,0}，{2,1,0}，{1,0,2}，{2,0,1}，{0,2,1}，{1,2}，{2,1}。
数据范围：
对于 20% 的数据 ，n≤20，m≤5。
对于 40%的数据 ，n≤300，m≤10。
对于 70 %的数据， n≤10^18，m≤20。
对于 100% 的数据， n≤10^18，m≤100。
君と彼女の恋
f[i][j]表示有i个元素，取模m余数和为j。f[i][j]=dp[i-1][j-k]。
然后统计所有f[i][j]满足n-j能被m整除，对答案的贡献即为i!*c[(n-j)/m+i-1][i-1]。
最后推一推，能约分，不用求出逆元也能过。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define ll long long 5 #define mod 905229641 6 using namespace std; 7 8 ll c(ll x,ll y) 9 { 10 ll ret=1; 11 for(int i=x-y+1;i<=x;i++) 12 { 13 ret=(ret*i)%mod; 14 } 15 return ret; 16 } 17 18 ll cal(int x,int y) 19 { 20 return c(y-1+x,y-1); 21 } 22 23 ll n; 24 ll m; 25 ll f[105][10005]; 26 27 int main() 28 { 29 freopen("jr.in","r",stdin); 30 freopen("jr.out","w",stdout); 31 scanf("%I64d%I64d",&n,&m); 32 f[0][0]=1; 33 for(ll i=0;i<m;i++) 34 { 35 for(ll j=i;j>=0;j--) 36 { 37 for(ll k=i*(i-1)/2;k>=0;k--) 38 { 39 f[j+1][k+i]=(f[j+1][k+i]+f[j][k])%mod; 40 } 41 } 42 } 43 ll ans=0; 44 for(ll i=1;i<=m;i++) 45 { 46 for(ll j=n%m;j<=n&&j<=m*(m-1)/2;j+=m) 47 { 48 ans=(ans+f[i][j]*i%mod*cal((n-j)/m%mod,i)%mod)%mod; 49 } 50 } 51 printf("%I64d ",ans); 52 fclose(stdin); 53 fclose(stdout); 54 return 0; 55 }
T2 bzoj 4715 囚人的旋律
Description
我们令a[i]表示看守的第i扇门对应囚犯的哪一扇门。令图G为有n个节点的图，编号为1～n。对于满足1≤i<j≤n的一对i和j，如果有a[i]>a[j]，那么在G中编号为i和j的节点之间连一条边。得到的图G被称为逆序图。对于图G=(V,E)，非空点集S∈V是一个独立集当且仅当对于任意两个点u,v∈V，不存在(u,v)∈E。而S是一个覆盖集当且仅当对于任意点v?S存在点u∈S满足(u,v)∈E。我们在意的是，图G中有多少个点集既是独立集又是覆盖集。出于某种不知名的原因，被迫参加监狱游戏的大家的安危和这个问题的答案有关。拜托了，请一定要求出这个方案数。Input
输入第一行含有两个整数n和m，表示逆序图的点数和边数。接下来m行，每行描述一条边。每行包含两个1～n的整数，代表边的两个端点。保证没有重边和自环。保证给定的图是一个合法的逆序图，即，存在至少一个序列，按照题目描述中所述方法得到的逆序图是给定的图。n≤1000，0≤m≤(n(n-1))/2Output
输出一个整数，表示方案数对1,000,000,007取模得到的结果。Sample Input
5 5
2 4
2 5
1 4
3 4
3 5Sample Output
3
网上的做法都是把a[i]求出来了。
JR给了我们一个新思路，即不用求出a[i]，利用邻接矩阵能O(1)判断两个元素之间是否连边。
最后O(n^2)求出a[i]的上升子序列即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mod 1000000007 5 using namespace std; 6 7 int n,m; 8 int e[1005][1005]; 9 int f[1005]; 10 11 int main() 12 { 13 freopen("is.in","r",stdin); 14 freopen("is.out","w",stdout); 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=m;i++) 17 { 18 int ff,tt; 19 scanf("%d%d",&ff,&tt); 20 e[ff][tt]=e[tt][ff]=1; 21 } 22 f[0]=1; 23 for(int i=0;i<=n+1;i++) 24 { 25 int t=0; 26 for(int j=i+1;j<=n+1;j++) 27 { 28 if((e[t][j]||(!t))&&(!e[i][j])) 29 { 30 f[j]=(f[j]+f[i])%mod; 31 t=j; 32 } 33 } 34 } 35 printf("%d",f[n+1]); 36 fclose(stdin); 37 fclose(stdout); 38 return 0; 39 }
T3 CF833B 题目传送门
jr的帅气魔法
handsome.cpp/.c/.pas
题目描述：
jr实在是太帅了！当然，那是有原因的。jr有一个变帅法阵，其中有n个法力水晶，编号1~n，每块法力水晶的法力参数为a[i]，jr会将这些法力水晶分成k组（一组内水晶必须连续），每组获得的效益为该组不同的法力水晶数（两块法力水晶是不同的当且仅当它们的法力参数不同），法阵的总效益为每组效益之和。jr想知道他能获得的最大效益。
输入(handsome.in)：
第一行两个整数n,k,代表有n个法力水晶，最多分k组。
下一行有n个正整数，为a[1],a[2],......a[n]。
输出(handsome.out)：
输出一行一个整数，为jr获得的最大效益。
handsome0.in：
handsome0.out：
8 3
7 7 8 7 7 8 1 7
6
数据范围：
20%的数据满足n<=90;
30%的数据满足n<=900;
100%的数据满足n<=35000,k<=50,a[i]<=n。
注：本题数（kun）据（bang）极（ce）水（shi）
题意是，将一个长度为n的序列分成最多k块，每块的得分是块内数字的种类数，求出最大得分。
依旧还是DP。用一个线段树维护最优解。
1 #include<cstdio> 2 #include<algorithm> 3 #define N 35003 4 #define K 51 5 using namespace std; 6 7 int n,k,a[N],nxt[N],hd[N],vl[N<<2],col[N<<2],f[K][N]; 8 9 void build(int lb,int rb,int nx,int typ) 10 { 11 col[nx]=0; 12 if(lb==rb) 13 { 14 vl[nx]=f[typ][lb-1]; 15 return; 16 } 17 int mid=(lb+rb)>>1; 18 build(lb,mid,nx<<1,typ); 19 build(mid+1,rb,(nx<<1)|1,typ); 20 vl[nx]=max(vl[nx<<1],vl[(nx<<1)|1]); 21 } 22 23 void pushdown(int p) 24 { 25 if(!col[p])return; 26 col[p<<1]+=col[p]; 27 col[p<<1|1]+=col[p]; 28 vl[p<<1]+=col[p]; 29 vl[p<<1|1]+=col[p]; 30 col[p]=0; 31 } 32 33 void update(int lm,int rm,int aim,int lb,int rb,int nx) 34 { 35 if(lm<=lb&&rm>=rb) 36 { 37 vl[nx]+=aim; 38 col[nx]+=aim; 39 return; 40 } 41 pushdown(nx); 42 int mid=(lb+rb)>>1; 43 if(lm<=mid)update(lm,rm,aim,lb,mid,nx<<1); 44 if(rm>mid)update(lm,rm,aim,mid+1,rb,(nx<<1)|1); 45 vl[nx]=max(vl[nx<<1],vl[(nx<<1)|1]); 46 } 47 48 int query(int lm,int rm,int lb,int rb,int nx) 49 { 50 if(lm<=lb&&rm>=rb)return vl[nx]; 51 pushdown(nx); 52 int mid=(lb+rb)>>1; 53 int ret=0; 54 if(lm<=mid)ret=max(ret,query(lm,rm,lb,mid,nx<<1)); 55 if(rm>mid)ret=max(ret,query(lm,rm,mid+1,rb,(nx<<1)|1)); 56 return ret; 57 } 58 59 int main() 60 { 61 scanf("%d%d",&n,&k); 62 for(int i=1;i<=n;i++) 63 { 64 scanf("%d",&a[i]); 65 nxt[i]=hd[a[i]]; 66 hd[a[i]]=i; 67 } 68 for(int i=1;i<=k;i++) 69 { 70 for(int j=1;j<=n;j++) 71 { 72 update(nxt[j]+1,j,1,1,n,1); 73 f[i][j]=query(i,j,1,n,1); 74 } 75 build(1,n,1,i); 76 } 77 printf("%d ",f[k][n]); 78 return 0; 79 }
毒瘤出题人。哼。
反正我们机房老人们已经送他上表白墙了哈哈哈哈哈哈~