? ? ? ?模型挺好的dp題,其實這道題就是建一個模型然后就很容易想到遞推過程了,我們可以把每個人的描述,存到數組a中,a[l][r]表示左邊有l個,到第r個這個人所在一層停止。。。然后就可以寫出轉移狀態方程了。注意如果dp[i]>dp[j] && i < j ?則需要把dp[j]更新為dp[i]。
?
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define CLR(a, b) memset(a, b, sizeof(a)) using namespace std; const int N = 555; int a[N][N], dp[N]; int main() { //freopen("input.txt", "r", stdin); int n, i, j, l, r; while(scanf("%d", &n) != EOF) { CLR(a, 0); CLR(dp, 0); for(i = 0; i < n; i ++) { scanf("%d%d", &l, &r); a[l][n - r] ++; } for(i = 0; i < n; i ++) { for(j = n - i - 1; j >= 0; j --) { dp[n - j] = max(dp[n - j], dp[i] + min(n - j - i, a[i][n - j])); dp[n - j] = max(dp[n - j], dp[n - j - 1]); } } printf("%d\n", dp[n]); } }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
