摳了兩天的題，必須單獨開一篇博客
Y Mashmokh and ACM
題意：序列a1, a2, …, an，如果滿足ai%ai-1 == 0 ( 2 <= i <= n )，就是好序列，給定n和k，n表示1～n的數，求長度為k的好序列的個數，答案對1e9+7取模，
由數1～n和長度k，聯想到狀態為以數j結尾，長度為i，構建二維陣列dp[i][j]來表示，狀態的值為以1～j，最大結尾數字為j，長度為i(以i個數字構成)的好序列個數(錯誤的狀態值，正確的在后面)
第一次嘗試，沒大有思路，畫了一個圖來幫助理解：
串列示以哪個數字結尾，行表示由幾個數字構成，每格表示結尾數字之前的所有可能組合
沒看出什么規律來，第二次嘗試，把每一格的數單獨列出來找規律
依然是沒有什么規律，這種方法行不通，想了好久也沒什么新思路，去看了一些其他人的題解，都說是水題，為啥我摳了這么久都沒摳出來，自己好菜喲，結合其他人的思路，在我原圖的基礎上做了一下改進(忽略掉我的丑字）
我們只用到涂藍色的數，鉛筆忽略，藍色的表示比前一列多的種類，藍色末位描黑的數表示在已經構建好的位數(沒描黑）基礎上，加上這一位數，舉個例子：比如3行4列的格，藍色的那些數是由2行1列，2行2列，2行4列的藍色數在末尾+4構建成的，選取1列2列4列是因為其能被4整除，符合題意，所以狀態的值應為以j結尾(結尾數字必須為j)，由i個數構成的方案數
這樣就好構建動態轉移方程了：
d[i+1][k]=(d[i+1][k]+d[i][j])%mod
k用來表示j的倍數
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int mod=1e9+7;
int d[2005][2005];
int main()
{
int n,m,i,j,k;
while(cin>>n>>m)
{
memset(d,0,sizeof(d));
d[0][1]=1;
for(i=0; i<=m; i++)
{
for(j=1; j<=n; j++)
{
for(k=j; k<=n; k+=j)
{
d[i+1][k]=(d[i+1][k]+d[i][j])%mod;
}
}
}
int ans=0;
for(i=1; i<=n; i++)
{
ans=(ans+d[m][i])%mod;
}
cout<<ans<<endl;
}
return 0;
}
附兩張圖
啥時候我也能輕輕松松寫出正確代碼，然后在做題總結的開頭，自信滿滿的寫上兩個大大的字—水題🤔
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/277343.html
標籤：其他
上一篇：2021-04-17