AtCoder Educational DP Contest B - Frog 2

這題是A-Frog 1的加強版
不過多一個迴圈還是輕鬆解決
以下為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,k;
cin>>n>>k;
vector<int> v(n),dp(n,1e9);
for(int i=0;i<n;i++)
cin>>v[i];
dp[0]=0;
for(int i=1;i<n;i++)
for(int j=1;j<=k;j++)
if(i-j>=0) dp[i]=min(dp[i-j]+abs(v[i]-v[i-j]),dp[i]);
cout<<dp[n-1]<<'\n';
}

留言

張貼留言

這個網誌中的熱門文章

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 ' ; }
閱讀完整內容