一直忙着複習，是以好久好久沒寫題解了。
暑假集訓開始了，開始寫題解吧，順便有自己的一個計劃，會在部落格中展現的：
cf #240 div2 D
D. Mashmokh and ACM
Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn’t able to solve them. That’s why he asked you to help him with these tasks. One of these tasks is the following.
A sequence of l integers b1, b2, …, bl (1 ≤ b1 ≤ b2 ≤ … ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all i (1 ≤ i ≤ l - 1).
Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).
Input
The first line of input contains two space-separated integers n, k (1 ≤ n, k ≤ 2000).
Output
Output a single integer — the number of good sequences of length k modulo 1000000007 (109 + 7).
input
3 2
output
5
題意： 就是說輸入n,k； 問你在1-n中 長度為k的有效序列有多少個， 有效序列的定義 就是 非遞減序列，1<=ai<=n 且ai+1 % ai ==0， 也就是每一個序列中的數都是前一個的整數倍。
分析： 這種題目需要我們慢慢推理： 不能急也不能慌，感覺上是肯定能做的。
首先 這個序列 自然是與n息息相關， 自然和長度k 也有關系。
而且 n 和n-1 的序列必然也是 有關系的， 由此我們細想一會兒不難想到是狀态的轉移，既然想到這方面必然就得思考怎麼建立dp與轉移方程。
不妨設 dp[i ][ j ]代表 以i為結尾的 長度為j的最大值； 那麼想想若是i,j+1 呢？ 我們可以在原來的長度為j的後面加一個i即可， 說明 dp[i][j+1] >=dp[i][j]。 那麼i 的整數倍 也是如此：dp[i*k][j+1]>dp[i][j];
不難得到結果；
int main()
{
//freopen("1.txt","r",stdin);
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) //所有長度為1，以i結尾的都一種
dp[i][1]=1;
for(int j=1;j<k;j++){
for(int i=1;i<=n;i++){
if(dp[i][j])
for(int len=i;len<=n;len+=i){
//長度為j+1，以 i的倍數 結尾的必然包含長度為j 以i結尾的種數
// 因為在後面加上一個i的倍數 即可
dp[len][j+1]+=dp[i][j],dp[len][j+1]%=MOD;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){ //所有長度為k的，以1-n結尾的
ans+=dp[i][k],ans%=MOD;
}
printf("%d\n",ans);
return 0;
} 一場GYM 試試手而已，最後還是沒有AK
2016 Al-Baath University Training Camp Contest-1 I. March Rain
題意：
由一串序列1-n來表示屋頂，在這個屋頂上會給你洞，然後你最多使用k塊闆子， 每一塊闆子的長度都可以自由更改，可以不同，然後問闆子中 最長的闆子 最小值是多少？
最小化最大值，咋一想覺得是貪心，但是最後20+分鐘想了一會兒貪心覺得想不出來， 往正解上想到了，但是并沒有時間敲and debug了。 其實二分也可以看成一種貪心， 我們隻需要二分闆子的長度（1-1e9），然後判斷在這個長度下，闆子夠不夠用即可
using namespace std;
int pos[1000005];
int p[1000005];
int work(int n,int len){
int cnt=0;
int ans=0;
for(int i=1;i<=n;i++){
if(pos[i]>cnt){
// printf("dong =%d ",pos[i]);
ans++;
cnt=pos[i]+len-1;
// printf("%d %d\n",cnt,pos[i]);
}
}
return ans;
}
int main(){
int t;
//freopen("1.txt","r",stdin);
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&pos[i]);
int l=1;
int r=pos[n];
while(l<r){
int mid=(l+r)/2; //現在長度為mid
// printf("%d %d %d\n",l,r,work(n,mid));
if(work(n,mid)> k){ //長度不夠，需要>cnt塊
l=mid+1;
}
else
r=mid;
}
printf("%d\n",l);
}
return 0;
} J X and Beasts
這個題就是一個最大遞增子序列問題，不是最長而是最大，由于n*n可以過，就随便寫了寫
using namespace std;
int f[1000005];
int x[105],y[105];
void work(){
mem(f);
for(int i=2;i<=1000000;i*=2){
for(int j=1;j*i<=1000000;j++){
f[i*j]++;
}
}
// for(int i=1;i<=100;i++){
// printf("%d %d\n",i,f[i]);
// }
}
int dp[105];
int main(){
//freopen("1.txt","r",stdin);
work();
int t;
scanf("%d",&t);
while(t--){
int n;
int sum=0;
scanf("%d",&n);
int pre=0;
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
//x[i]=f[x[i]];
}
for(int i=1;i<=n;i++){
int maxn=0;
for(int j=i-1;j>=1;j--){
if(x[i]>x[j]){
maxn=max(maxn,dp[j]);
}
}
dp[i]=f[x[i]]+maxn;
}
for(int i=1;i<=n;i++)
sum=max(sum,dp[i]);
printf("%d\n",sum);
}
return 0;
}