#include #include #include #include #include #include #include #include #include #include #include using namespace std; int dp[10][3]; //dp[i][j] 表示數字的位數，j代表狀態 //dp[i][0] 表示不存在不吉利的數字 //dp[i][1] 表示不存在吉利數字，且最高位是2 //dp[i][2] 表示存在不吉利數字 void init(){ memset(dp,0,sizeof(dp)); dp[0][0] = 1;//初始化一下0位的不吉利數字為1 for(int i = 1;i <= 7;i++){ dp[i][0] = dp[i-1][0]*9 - dp[i-1][1];//最高位不含有4的9個數字，而且因為當放第i位放6的時候，i-1不能放2所以要減去一下i-1位不存在不吉利數字切最高位為2 的情況 dp[i][1] = dp[i-1][0];//最高位放了2其他位只要不是不吉利數字就可以 dp[i][2] = dp[i-1][2] * 10 +dp[i-1][0] + dp[i-1][1];//i位的含有不吉利數字的個數是i-1位的含有不吉利數字的×10,因為只要後面含有不吉利數字前面不管是什麼都可以所以前面×10,另外如果最高位放一個4然後後面的全部不是不吉利數字就行，還可以是最高位放上一個6然後，倒數第二位放上2就可以的不是不吉利就行 } } int fun(int n){ int len = 0,tem = n,ans,flag,a[10]; while(n){ a[++len] = n%10; n /= 10; } a[len+1] = ans = 0; flag = 0; //求出1-(n-1)之間的不吉利的數 for(int i = len;i >= 1;i--){ ans += dp[i-1][2] * a[i];//後面的i-1是不吉利數字之後前面就可以填上任意的 if(flag){ ans += dp[i-1][0] * a[i]; } if(!flag && a[i] > 4){ ans += dp[i-1][0];//如果a[i]>4那麼就可以在i位上放上一個4 } if(!flag && a[i+1] == 6 && a[i] > 2){//如果後一位是6這一位是大於2的 ans += dp[i][1]; } if(!flag && a[i] > 6){ ans += dp[i-1][1]; } if(a[i] == 4 || a[i+1] == 6 && a[i] == 2){ flag = 1; } } return tem - ans; } int main() { int n,m; init(); while(cin >> n >> m,n||m){ printf("%d\n",fun(m+1) - fun(n)); } return 0; }
首先，混合編程不是指在同一個文件裡寫C與C+&
bzoj4518--斜率優化DP，bzoj4518--斜率d
建議和規則 建議： 理解編譯器所使用的數據模型 使用
先總結下為什麼要進行單元測試： 1 錯誤盡早發現，這是
輸入整數n（n<=10000），表示接下來將會輸入n個
在C++語言中一個函數可以調用其他函數，在設計良好的C++
