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

1樓：

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

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

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

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

最後偷偷配上一組錯資料，事就成了。

2樓：

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

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

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

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

3樓：Yuchong Pan

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

狀態設計

狀態轉移

資料結構優化DP

其他方法優化DP

演算法實現難度

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

4樓：

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

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

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

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

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

5樓：李maybe

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

1.讓模型更加隱蔽，不要讓別人一看到就知道是乙個動態規劃的題目。比如一般動態規劃很注重一種動態規劃的「順序」，而如果題目在表面上來看不存在這種明顯DP順序，而需要仔細琢磨問題的性質而創造出一種特殊的順序。

這樣就會給解題者帶來一些障礙，或者說不會讓人那麼快就知道，這道題肯定是動態規劃問題。

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

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