ZJ d887: 1.山脈種類(chain) - 7月 04, 2019


計算可行的數量,用DP求解
(圖為題目範例中n=3的情況)

可知上坡的數量≥於下坡的數量
於是可畫出上圖
得狀態轉移式為
dp[i][j]=dp[i-1][j]+dp[i][j-1]
以下為code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()
{
AC
ll n,dp[26][26];
memset(dp,0,sizeof(dp));
fill(dp[0],dp[0]+26,1);
for(ll i=1;i<26;i++)
for(ll j=i;j<26;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
while(cin>>n)
cout<<dp[n][n]<<'\n';
}
要是沒看過這種推上下坡的寫法完全想不出答案...
DP也太難了吧
還有這次又被忘記初始化陣列給卡住了
下次還要注意一點

留言

張貼留言

這個網誌中的熱門文章

TIOJ 1080 . A.逆序數對 (BIT解法)

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1080 先做一波離散化 把所需的BIT長度壓到10⁵以內 而後就記錄目前放了幾個數字進BIT 用放了幾個數字減去有幾個數字比當前輸入的數字小(BIT存的) 就是當前的逆序數對 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); #define lowbit ( x ) x &- x ll n; struct BIT { vector < ll > v; void modify ( ll x , ll val ) { for (;x < v. size ();x += lowbit (x)) v[x] += val; } ll query ( ll x ) { ll t = 0 ; for (;x;x -= lowbit (x)) t += v[x]; return t; } }; int main () { AC ll num = 1 ; while (cin >> n && n) { cout << " Case # " << num ++<< " : " ; ll cnt = 0 ,r = 0 ,rnk = 1 ; BIT sum; vector < ll > v (n); set < ll > s; ...
閱讀完整內容

ZJ d718: Waiting In Line

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d718 這題是模擬排隊 不過有一個插隊的情況 於是我們用list取代queue 我們用一個unordered_map去存這些人分別屬於哪些團體 方便之後查詢 再來我們用一個vector去存這些團體是否在list中 在的話就進行插隊 而插隊我們用一個vector去存現在這個隊伍中每個團體的最後一個人所在的iterator 就解決啦 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,m,t,cnt = 1 ; while (cin >> n) { cout << " Line # " << cnt ++<< ' \n ' ; unordered_map <int , int> um; for ( int i = 0 ;i < n;i ++ ) { cin >> m; for ( int j = 0 ;j < m;j ++ ) { cin >> t; um[t] = i; } } string s; list <int> l; vector <int> v (n + 1 , 0 ); vector ...
閱讀完整內容

AtCoder Educational DP Contest E - Knapsack 2

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_e 這題還蠻有趣的 他的重量開到10⁹導致不能用上一題(常規0/1背包)的做法去做 要把價值當做dp轉移,去找當前價值所需的最小重量 最後找到的最大的小於重量限制的價值就是答案 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,w,r = 0 ; cin >> n >> w; vector < ll > dp ( 100001 , 1 e 10 ); dp[ 0 ] = 0 ; for ( int i = 0 ;i < n;i ++ ) { int wei,val; cin >> wei >> val; for ( int j = 100000 ;j >= val;j -- ) dp[j] = min (dp[j],dp[j - val] + wei); } for ( int i = 1 ;i < dp. size ();i ++ ) if (dp[i] <= w) r = i; cout << r << ' \n ' ; }
閱讀完整內容