自編一道動規題，可以從哪幾個方面增加難度?

12-31

一個線性動規，大概NOIP難度，編完之後發現過於簡單了，可以從哪些方面增加難度。

卡常數

比如說一道複雜度n^2的noip難度的題，你把n開到30w他就變成了WC難度的題。

我的看法是，一道題出了就出了，沒啥好增加難度的。往一個其實不難的題目上通過各種小技巧加難度其實是沒什麼意義的事情。

比如Belleve建議的加個Parsing的階段，「難度」當然提高了，但是這基本上等價於你出了兩個題，一個叫「Parse」，一個叫「DP」，然後判分標準變成了兩道題都做出來才有分……這種事情作為準備特定考試的考題的技巧是有用的，因為你可以把兩個知識點壓在一道題里，以及可以微調考題的思考時間和代碼量之間的比例。但是你也看出來了，本質上，那個「DP」題難度並沒變，變的只是「算分方式」……

給題目增加故事背景這件事，我覺得一般來說跟題目難度無關，而且要不要增加故事背景往往也是出於題目難度以外的考量，所以我覺得也不是很有用。當然，有時候增加故事背景是實現「轉換模型」（見下4）的好手段。

要加強難度的話，請考慮以下方式：

你現在的數據規模是不是足夠大？如果你的時限是1秒，但是你自己的程序在0.2秒以內就出解了，請考慮加大數據範圍。
自己仔細查閱資料，看看自己出的題自己已知的演算法是不是最優的？如果不是的話，請更新到你所能找到的最優秀的演算法，然後回到步驟1再看一遍這個列表。
思考下列問題：你的演算法能否推廣到更加一般的情況？你的問題能否增加一個條件，在特定前提下有更高效的解法？前一種情況下，如果你能推廣，得到的新題目往往比原來更難。後一種情況，回到步驟1。
這個演算法是否可以拿來解決一些其他看似不太相關的問題？如果能，你往往能獲得一個模型更加隱蔽的題，它應當比原題難。

當然我最推薦的思路是：重新出一道。

我只想說。。Oier何必難為Oier！

immortalCO大爺提供的幾種方法：

1、卡常數。比如通過優化可以把DP做到1/4常數，那麼把時限開成優化後代碼的兩倍。

2、卡內存。比如必須滾動數組，計數題取模DP數組只能開int，更坑點的話int開不下必須用short和char。

3、出成動態DP。比如序列DP，每次修改序列中的一個數，詢問DP值。

我出題時經常使用的幾種方法：

1、用另一個模型來包裝題目。常見的有：最小鏈覆蓋=最長反鏈，有的題最長反鏈很容易DP求，而最小鏈覆蓋不好直接求，這時候就把題目寫成求最小鏈覆蓋。

2、加入一些結論。比如有些分組問題最優解一定是每組為一段連續區間，證明出結論才能優化DP。

3、如果輸出方案比較困難，可以出成輸出方案。

在乎自己聲名的話建議換一道題，個人經驗是高質量的題目都是先想到了題，然後慢慢想出怎麼做。先想好做法再拼湊的題，無美感。

我覺得大概可以分成兩個大方向

1.讓模型更加隱蔽，不要讓別人一看到就知道是一個動態規劃的題目。比如一般動態規劃很注重一種動態規劃的「順序」，而如果題目在表面上來看不存在這種明顯DP順序，而需要仔細琢磨問題的性質而創造出一種特殊的順序。這樣就會給解題者帶來一些障礙，或者說不會讓人那麼快就知道，這道題肯定是動態規劃問題。

2.這個就和模型有很大的關係了，不過既然只是NOIP級別的話，可以稍微構造一點和本來要記錄的狀態相關聯的狀態，導致這些新構造的狀態可以不用完全記錄在動態規劃的狀態中，而是可以由其它狀態推導出來，從而減少動態規劃的複雜度。

不過我覺得動態規劃真的太靠模型了... 如果是有了一個動態規劃的模型，我覺得最好是繼續去剖析這個模型的性質從而設計更優的動態規劃方法。實在不行再去考慮單純的加難吧。

動態規劃的難點一般體現在如下幾個方面：

狀態設計
狀態轉移
數據結構優化DP
其他方法優化DP
演算法實現難度

因此，你可以從上面幾個方面來加強題目的難度。

拋開思考過程不談，在得知狀態表示和轉移方程後，大概還有這幾個難點：

1. 直接轉移複雜度過高，需要變換順序，通過記錄一些輔助值來降低複雜度。

2. 轉移方案可以使用數據結構維護，同樣可以降低轉移複雜度。

3. 轉移方程可以變換為某種特定形式，可以通過斜率優化、四邊形不等式優化等降低複雜度。

當然，NOIP難度的話，第一種就差不多了...

告訴你哦，只要你 IO 用 JSON 或者 XML，保證搞死一群 oier

曾經出過NOIP，不過貌似沒出過直接考DP的題目。

個人覺得可以考慮下面兩個方面：

1.更複雜的狀態（多維狀態、插頭DP等）

2.轉移優化（斜率優化、四邊形優化、矩陣快速冪等）

斜率優化

把DP域拽到日期上，要求他們判閏年，狠一點的可以要求把1582年10月5日—1582年10月14日那消失的10天也考慮進去。

輸入輸出要求使用羅馬數字，或者輸入上套一層表達式求值。

要求輸出方案，還要求方案的字典序最小。

把題面描述寫得含糊其辭可以有多種理解，把樣例出得怎麼理解都是對的。

最後偷偷配上一組錯數據，事就成了。

如果是在OJ上面判題的話

測試數據直接上一個數量級就好了