轉(zhuǎn)自? https://www.cnblogs.com/y142857/p/7134366.html

?

首先想到設(shè)f[i][j]表示到第i行第j列所需要的最少點(diǎn)擊屏幕次數(shù)。轉(zhuǎn)移方程為

f[?i?][?j?]=min{f[?i-1?][?j?-?k*x[i-1]?]?+?k}?(1<=?k?<=?j/x)?上升——①

f[?i?][?j?]=min{f[?i-1?][?j?+?y[i-1]?}??(?j?+?y[i-1]?<=?m)?下降

顯然，下降可以O(shè)(1)轉(zhuǎn)移，主要問題在上升的轉(zhuǎn)移。

我們將上升的方程變一下：

f[?i?][?j?-?x[i-1]?]=min{f[?i-1?][?(j?-?x[i-1])?-?(k-1)*x[i-1]?]?+?k?-1}?——②

這是?f[?i?][?j?-?x[i-1]?]?的轉(zhuǎn)移。

由?②?化簡(jiǎn)可得：

f[?i?][?j?-?x[i-1]?]=min{f[?i-1?][?j?-?k*x[?i-1]?]?+?k?-1}——③

由①③消去f[?i-1?][?j?-?k*x[?i-1]?]+k可得

f[?i?][?j?]=?f[?i?][?j?-?x[?i-1?]?]+1

于是就可以O(shè)(n*m)的時(shí)間內(nèi)出解

?

#include<bits/stdc++.h> using namespace std; int dp[10005][2005], low[10005], hi[10005], a[10005], b[10005], to[10005]; int ans, n, m, k, x, l1, l2; int main() {cin >> n >> m >> k;for(int i = 1; i <= n; i++)cin >> a[i] >> b[i];for(int i = 1; i <= n; i++){low[i] = 1;hi[i] = m;}for(int i = 1; i <= k; i++){cin >> x >> l1 >> l2;to[x] = 1;low[x] = l1+1;hi[x] = l2-1;}memset(dp, 0x3f, sizeof(dp));for(int i = 1; i <= m; i++)dp[0][i] = 0;for(int i = 1; i <= n; i++){for(int j = a[i]+1; j <= m+a[i]; j++)dp[i][j] = min(dp[i][j-a[i]]+1, dp[i-1][j-a[i]]+1);for(int j = m+1; j <= m+a[i]; j++)dp[i][m] = min(dp[i][m], dp[i][j]);for(int j = 1; j <= m-b[i]; j++)dp[i][j] = min(dp[i][j], dp[i-1][j+b[i]]);for(int j = 1; j < low[i]; j++)dp[i][j] = 0x3f3f3f;for(int j = hi[i]+1; j <= m; j++)dp[i][j] = 0x3f3f3f;}ans = 0x3f3f3f;for(int i = 1; i <= m; i++) ans = min(ans, dp[n][i]);if(ans < 0x3f3f3f) {cout << "1" << endl << ans;return 0;}int i, j;for(i = n; i >= 1; i--){for(j = 1; j <= m; j++)if(dp[i][j]<0x3f3f3f) break;if(j <= m) break;} ans = 0;for(int j = 1; j <= i; j++)if(to[j]) ans++;cout << "0" << endl << ans;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lovezxy520/p/11386316.html

總結(jié)

以上是生活随笔為你收集整理的【题解】luogu P1941 飞扬的小鸟的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。