UESTC 250 windy數 數位dp

題目鏈接

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem1(a) memset(a, -1, sizeof(a))
 4 #define ll long long
 5 int dp[20][20], digit[20], len;
 6 ll dfs(int len, int pre, bool fp, bool first) {     //first表示前面的數是否全部為0, pre是前一個數
 7     if(!len)
 8         return 1;
 9     if(!first&&!fp && dp[len][pre]!=-1)
10         return dp[len][pre];
11     int ret = 0, maxx = fp?digit[len]:9;
12     for(int i = 0; i<=maxx; i++) {
13         if(!first)
14             if(abs(i-pre)<2)
15                 continue;
16         ret += dfs(len-1, i, fp&&i == maxx, first&&i==0);
17     }
18     if(!fp&&!first)
19         return dp[len][pre] = ret;
20     return ret;
21 }
22 int cal(int n) {
23     len = 0;
24     while(n) {
25         digit[++len] = n%10;
26         n/=10;
27     }
28     return dfs(len, 0, true, true);
29 }
30 int main()
31 {
32     int a, b;
33     mem1(dp);
34     while(~scanf("%d%d", &a, &b)) {
35         printf("%d\n", cal(b)-cal(a-1));
36     }
37 }

?

轉載于:https://www.cnblogs.com/yohaha/p/5035226.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/458577.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/458577.shtml
英文地址,請注明出處:http://en.pswp.cn/news/458577.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

c語言面試題大全

C語言面試題大匯總 4. static有什么用途&#xff1f;&#xff08;請至少說明兩種&#xff09; 1.限制變量的作用域(DL:使其只在定義的當前文件中起作用&#xff0c;static是只能由與變量在同一個文件中定義的程序存取的全局變量。也就是說使全局變量成為文件的私有變量&#…

WindowsAPI詳解——GetCurrentDirectory 獲得程序當前目錄

每個Windows程序都有一個自己的當前目錄&#xff0c;默認是程序exe文件所在的目錄。系統在給程序加載動態鏈接庫文件(DLL)時先在程序當前目錄里查找要加載的DLL&#xff0c;如果在此目錄下沒有找到系統便會去Windows目錄下查找。在這兒我們主要將如何獲得程序的當前目錄&#x…

20151210小問題2

1、各瀏覽器下 scrollTop的差異 IE6/7/8&#xff1a; 對于沒有doctype聲明的頁面里可以使用 document.body.scrollTop 來獲取 scrollTop高度 &#xff1b; 對于有doctype聲明的頁面則可以使用 document.documentElement.scrollTop&#xff1b; Safari: safari 比較特別&#x…

限制MySQL Binlog的傳輸速率

最近一臺核心庫備庫完成恢復后打開slave&#xff0c;導致主庫傳送binlog&#xff0c;瞬間占滿網絡&#xff0c;觸發故障。 為了做一些限制&#xff0c; 給mysql在發送binlog的函數(mysql_binlog_send)里每隔一段時間sleep一次&#xff0c; 增加了兩個參數&#xff1a; master_s…

sprintf用法詳解

printf可能是許多程序員在開始學習C語言時接觸到的第二個函數&#xff08;我猜第一個是main&#xff09;&#xff0c;說起來&#xff0c;自然是老朋友了&#xff0c;可是&#xff0c;你對這個老朋友了解多嗎&#xff1f;你對它的那個孿生兄弟sprintf了解多嗎&#xff1f;在將各…

掌握 Ajax,第 2 部分: 使用 JavaScript 和 Ajax 發出異步請求

轉http://www.ibm.com/developerworks/cn/xml/wa-ajaxintro2/ 掌握 Ajax&#xff0c;第 2 部分: 使用 JavaScript 和 Ajax 發出異步請求 在 Web 請求中使用 XMLHttpRequest 多數 Web 應用程序都使用請求/響應模型從服務器上獲得完整的 HTML 頁面。常常是點擊一個按鈕&#xff0…

Provisioning Services 7.8 入門系列教程之十一 通過版本控制自動更新虛擬磁盤

續Provisioning Services 7.8 入門系列教程之十 通過類自動更新虛擬磁盤從前兩的兩種更新方式可以看出&#xff0c;它們有一個共同的特點&#xff0c;即需要產生&#xff08;復制&#xff09;完成的虛擬磁盤副本&#xff0c;然后進行相關的升級操作。這兩種方法在實際生產中&am…

OC面試題

什么是KVC和KVO&#xff1f; 答&#xff1a;KVC(Key-Value-Coding)內部的實現&#xff1a;一個對象在調用setValue的時候&#xff0c; &#xff08;1&#xff09;首先根據方法名找到運行方法的時候所需要的環境參數。 &#xff08;2&#xff09;他會從自己isa指針結合環境參數&…

【算法】QuickSort

快速排序&#xff0c;時間復雜度O(N*logN)&#xff0c;要能熟練掌握&#xff01; 以下主要參考http://blog.csdn.net/morewindows/article/details/6684558&#xff0c; 感謝原博主&#xff01; 該方法的基本思想是&#xff1a; 1&#xff0e;先從數列中取出一個數作為基準數。…

串口之GetCommState、SetCommState函數詳解

GetCommState 讀取串口設置(波特率,校驗,停止位,數據位等).函數聲明&#xff1a;BOOL GetCommState(HANDLE hFile,LPDCB lpDCB);GetCommState函數的第一個參數hFile是由CreateFile函數返回指向已打開串行口的句柄。第二個參數指向設備控制塊DCB。如果函數調用成功&#xff0c;則…

登錄失敗時記住訪問的地址

登錄失敗時記住訪問的地址 使用spring MVC 訪問時,在攔截器中記錄訪問的地址: Java代碼 String path request.getRequestURI();//"/demo_channel_terminal/news/list" System.out.println("您無權訪問:" path); //用于登錄成功…

串口之GetCommTimeouts、SetCommTimeouts函數詳解

Windows系統利用此函數獲取特定的通訊設備讀寫時的超時參數設定&#xff0c;GetCommTimeouts函數聲明如下&#xff1a;BOOL GetCommTimeouts(HANDLE hFile,LPCOMMTIMEOUTS lpCommTimeouts);GetCommTimeouts函數的第一個參數hFile是由CreateFile函數返回指向已打開串行口的句柄。…

GUN/LINUX命令之 cp mv install

1. cp命令 復制copy命令的簡寫 SYNOPSIS cp [OPTION]... [-T] SOURCE DEST cp [OPTION]... SOURCE... DIRECTORY cp [OPTION]... -t DIRECTORY SOURCE... cp SOURCE DEST 后者如果是目錄那么源文件就復制到文件夾里面并且保持著原來的名字&#xff1b;如果D…

Tomcat - Maven plugin: 運行找不到webapp

2019獨角獸企業重金招聘Python工程師標準>>> The tomcat7-maven-plugin allows running the current project as a Web application and additional <webapps> can be specified that will be simultaneously loaded into tomcat. My project is not a Web ap…

面試題3

1. 你如何理解 iOS 內存管理 1. new alloc copy retain這些對象我們都要主動的release或者 autorelease 2. 如果是類方法創建的對象,那么系統自動釋放池自動在適當的 時候會幫我們 release 3. ARC xcode 自動會幫我們人工智能的添加 release autorelease 操 作 2. C語言里的數…

基于MQTT協議進行應用開發

來自&#xff1a;http://www.cnblogs.com/secondtononewe/p/6073089.html 官方協議有句如下的話來形容MQTT的設計思想&#xff1a; “It is designed for connections with remote locations where a "small code footprint" is required or the network bandwidth i…

SortedDictionaryTKey,TValue正序與反序排序及Dicttionary相關

SortedDictionary<TKey,TValue>能對字典排序 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace SortDictionary {class Program{static void Main(string[] args){TestDictionarySort();…

DOS窗口的編碼頁從UTF-8調回GBK

2019獨角獸企業重金招聘Python工程師標準>>> 之前在DOS窗口操作MySQL數據庫的時候&#xff0c;將編碼頁從GBK設置成了UTF-8&#xff0c;解決了在DOS窗口顯示MySQL數據庫中的表中的中文字符出現亂碼的問題。但是除此之外&#xff0c;DOS窗口顯示的其他中文字符都是亂…

UIBezierPath

學習UIBezierPath畫圖 筆者在寫本篇文章之前&#xff0c;也沒有系統學習過貝塞爾曲線&#xff0c;只是曾經某一次的需求需要使用到&#xff0c;才臨時百度看了一看而且使用最基本的功能。現在總算有時間停下來好好研究研究這個神奇而偉大的貝塞爾先生&#xff01; 筆者在學習時…

系統架構設計理論與原則

一、無共享架構 1、無共享架構 無共享架構是一種分布式計算架構&#xff0c;這種架構中不存在集中存儲的狀態&#xff0c;系統中每個節點都是獨立自治的&#xff0c;整個系統中沒有資源競爭&#xff0c;這種架構具有非常強的擴張性&#xff0c;目前在web應用中被廣泛使用。 無共…