thảo luận Leetcode mỗi ngày

@chiyeuemthoi Nộp bài thử nào bạng.
iErjo0A.png

C++: 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define i64 long long
typedef vector<i64> vi;
typedef pair<i64,i64> pii;
typedef double ld;
typedef unsigned long long ull;
typedef tree<i64, null_type, less_equal<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main(){
    faster();
    int t;
    cin>>t;
    while(t--){
        int n, ins, del, cop;
        cin>>n>>ins>>del>>cop;
        int dp[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=min(dp[i-1]+ins,(i%2==0?dp[i/2]+cop:dp[(i+1)/2]+cop+del));
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}
 
Đảng viên Hanni said:
@chiyeuemthoi Nộp bài thử nào bạng.
iErjo0A.png

C++: 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define i64 long long
typedef vector<i64> vi;
typedef pair<i64,i64> pii;
typedef double ld;
typedef unsigned long long ull;
typedef tree<i64, null_type, less_equal<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main(){
    faster();
    int t;
    cin>>t;
    while(t--){
        int n, ins, del, cop;
        cin>>n>>ins>>del>>cop;
        int dp[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=min(dp[i-1]+ins,(i%2==0?dp[i/2]+cop:dp[(i+1)/2]+cop+del));
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}
Click to expand...
Logic này không tính đến trường hợp delete, dp = Min(...,dp[i+1] + del) => Ko chính xác
Nói chung dp ko áp dụng vào đây được vì tính có logic i từ i+1
 
Đảng viên Hanni said:
đầu tiên, tại vị trí i đang xét, chia mảng ra làm 2 phần. Từ 0 đến i-1 và từ i+1 đến n-1.
Giờ làm sao để 0->i-1 đi lên i+1->n-1? Không quan trọng quá trình, mà quan trọng thao tác cuối là gì, chắc chắn không phải delete, vì nếu delete là bước cuối thì không thể vượt qua i được, cũng không phải insert, vì nếu insert thì chỉ tối đa đến i thôi.
06wkMvn.png

ok vậy thao tác cuối là copy. Vậy tại sao ta chỉ quan tâm đến copy lên i+1? Vì sao không quan tâm i+3, i+5, i+7,...? (copy *2 luôn bằng chẵn vì vậy không có vụ i+2, i+4,... nhé). Ví dụ i+3, delete 2 lần về i+1, thì ở (i+3)/2, ta delete 1 lần là về (i+1)/2 rồi. Nói cách khác, thay vì phải delete x lần, ta chỉ cần quay về thao tác trước copy, delete x/2 lần. => Chỉ cần xét i+1.
9S282dK.png

Công thức dp ban đầu:
lẻ: dp=min(dp[i-1]+insert,dp[i+1]+delete)
chẵn: dp=min(dp[i-1]+insert,dp[i+1]+delete,dp[i/2]+copy)
(không thể qhđ)
tương đương:
lẻ: dp=min(dp[i-1]+insert,dp[(i+1)/2]+copy+delete)
chẵn: dp=min(dp[i-1]+insert,dp[i/2]+copy)
(có thể qhđ)
Click to expand...
đọc ný nuận này ko hiểu gì hết
LTT2cUR.png

kết quả cuối cùng thì cũng có vẻ khá giống của toy, chỉ tiết kiệm được bước min i chẵn = 2k+2 bỏ cái T(k+2) + Z + Y + Y đi, cái này toy thấy có vẻ khá bự nhưng ko ný nuận loại bỏ nó ra được
OANgL56.png

đọc lại thì thấy có vẻ có ný, k+2 bỏ 1 còn k+1, x2 thành 2k+2, tốn T(k+2) + Y + Z < T(k+2) + Z + Y + Y nhưng vẫn phải xét TH này chứ nhỉ
ghXpJrI.png
làm thao ný nuận i chẵn thì thao tác cuối ko phải là delete, ný nuận gì thặc khó hiểu
aVgiONl.png

toy vừa nghĩ ra, T(k+2) + Y vs T(k+1), vì k+1 < k+2 nên nếu T(k+2) + Y < T(k+1) thì nghĩa là T(k+1) chưa tối ưu: có thể gán T(k+1) = T(k+2) + Y. Nhưng đều này vô lý vì dp thì nếu a < b thì T(a) phải là tối ưu trước khi tới T(b) rồi, vì vậy T(k+2) + Y >= T(k+1), vậy T(k+2) + Y + Z >= T(k+1) + Z vậy nghĩa là ko cần xét TH delete ở i chẵn, toy ný nuận thặc toẹt vời
zFNuZTA.png
 
Last edited:
Đảng viên Hanni said:
@chiyeuemthoi Nộp bài thử nào bạng.
iErjo0A.png

C++: 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define i64 long long
typedef vector<i64> vi;
typedef pair<i64,i64> pii;
typedef double ld;
typedef unsigned long long ull;
typedef tree<i64, null_type, less_equal<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main(){
    faster();
    int t;
    cin>>t;
    while(t--){
        int n, ins, del, cop;
        cin>>n>>ins>>del>>cop;
        int dp[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=min(dp[i-1]+ins,(i%2==0?dp[i/2]+cop:dp[(i+1)/2]+cop+del));
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}
Click to expand...
sai fen ạ
 
thử code này xem, chắc phải đúng thoy nếu ko chắc hiểu xai đề
OANgL56.png


C++: 
#include <iostream>
#include <queue>
#include <unordered_set>
#include <utility>

int findTotalTime(int N, int X, int Y, int Z) {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minPQ;
    std::unordered_set<int> visited;
    minPQ.emplace(0, 0);
    while (!minPQ.empty()) {
        auto [totalTime, charLength] = minPQ.top();
        minPQ.pop();
        if (charLength == N) return totalTime;
        if (visited.count(charLength)) continue;
        // insert
        int nextLength = charLength + 1;
        if (visited.count(nextLength) == 0) minPQ.emplace(totalTime + X, nextLength);
        // delete
        nextLength = charLength - 1;
        if (nextLength > 0 && visited.count(nextLength) == 0) minPQ.emplace(totalTime + Y, nextLength);
        // copy
        nextLength = charLength * 2;
        if (visited.count(nextLength) == 0) minPQ.emplace(totalTime + Z, nextLength);
        //
        visited.emplace(charLength);
    }
}

int main() {
    int T, N, X, Y, Z;
    std::cin >> T;
    while (std::cin >> N >> X >> Y >> Z) std::cout << findTotalTime(N, X, Y, Z) << "\n";
}
 
Last edited:
Spaghetti Code said:
thử code này xem, chắc phải đúng thoy nếu ko chắc hiểu xai đề
OANgL56.png


C++: 
#include <iostream>
#include <queue>
#include <unordered_set>
#include <utility>

int findTotalTime(int N, int X, int Y, int Z) {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minPQ;
    std::unordered_set<int> visited;
    minPQ.emplace(0, 0);
    while (!minPQ.empty()) {
        auto [totalTime, charLength] = minPQ.top();
        minPQ.pop();
        if (charLength == N) return totalTime;
        if (visited.count(charLength)) continue;
        // insert
        int nextLength = charLength + 1;
        if (visited.count(nextLength) == 0) minPQ.emplace(totalTime + X, nextLength);
        // delete
        nextLength = charLength - 1;
        if (nextLength > 0 && visited.count(nextLength) == 0) minPQ.emplace(totalTime + Y, nextLength);
        // copy
        nextLength = charLength * 2;
        if (visited.count(nextLength) == 0) minPQ.emplace(totalTime + Z, nextLength);
        //
        visited.emplace(charLength);
    }
}

int main() {
    int T, N, X, Y, Z;
    std::cin >> T;
    while (std::cin >> N >> X >> Y >> Z) std::cout << findTotalTime(N, X, Y, Z) << "\n";
}
Click to expand...
đúng rồi bác ạ thanks bác bác giải thích code của bác dc ko :p:p
1679009868848.png
 
chiyeuemthoi said:
đúng rồi bác ạ thanks bác bác giải thích code của bác dc ko :p:pView attachment 1722181
Click to expand...
Dijkstra algorithm thoy
gvTwnV8.gif

coi mỗi độ dài là 1 vertex: 0 tới N' (N' có thể lớn hơn N)
mỗi vertex V có 3 edge tới V+1, V-1, 2V, mỗi edge có weight X, Y, Z tương ứng
rồi cứ thế mà chạy Dijkstra algo tìm đường đi ngắn nhất từ vertex 0 tới vertex N thoy
 
Last edited:
Bài hôm qua (16/3) đã từng giải dạng tương tự https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/. Thể loại này nếu chưa từng giải qua (hoặc nhớ hướng tiếp cận) thì với tui khá là rối não =((

Time: O(n)
Space: O(n) for stack memory and O(n) for a hashmap
Python: 
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        self.pos = {val: i for i, val in enumerate(inorder)}
        n = len(inorder)
        self.postorder = postorder
        self.idx = n-1
        
        return self.buildNode(0, n-1)
    
    def buildNode(self, left, right):
        if left > right:
            return
        
        val = self.postorder[self.idx]
        self.idx -= 1
        
        node = TreeNode(val)
        
        node.right = self.buildNode(self.pos[val]+1, right)
        node.left = self.buildNode(left, self.pos[val]-1)
        
        return node

Bài hôm nay
Time: Insert/Search/StartsWith O(n)
Space: Insert O(length of all letters stored)

Python: 
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        i = 0
        n = len(word)
        node = self.root
        while i < n:
            c = word[i]
            
            if c not in node.children:
                node.children[c] = Node()
                
            node = node.children[c]
            i += 1
        
        node.end = True

    def search(self, word: str) -> bool:
        node = self.searchEndNode(word)
        return node and node.end

    def startsWith(self, prefix: str) -> bool:
        return self.searchEndNode(prefix) is not None
    
    def searchEndNode(self, word):
        i = 0
        n = len(word)
        node = self.root
        while i < n:
            c = word[i]
            
            if c not in node.children:
                return None
                
            node = node.children[c]
            i += 1
        
        return node
        
class Node:
    def __init__(self):
        self.children = {}
        self.end = False
 
Symbiosis said:
Bài hôm qua (16/3) đã từng giải dạng tương tự https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/. Thể loại này nếu chưa từng giải qua (hoặc nhớ hướng tiếp cận) thì với tui khá là rối não =((

Time: O(n)
Space: O(n) for stack memory and O(n) for a hashmap
Python: 
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        self.pos = {val: i for i, val in enumerate(inorder)}
        n = len(inorder)
        self.postorder = postorder
        self.idx = n-1
       
        return self.buildNode(0, n-1)
   
    def buildNode(self, left, right):
        if left > right:
            return
       
        val = self.postorder[self.idx]
        self.idx -= 1
       
        node = TreeNode(val)
       
        node.right = self.buildNode(self.pos[val]+1, right)
        node.left = self.buildNode(left, self.pos[val]-1)
       
        return node

Bài hôm nay
Time: Insert/Search/StartsWith O(n)
Space: Insert O(length of all letters stored)

Python: 
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        i = 0
        n = len(word)
        node = self.root
        while i < n:
            c = word[i]
           
            if c not in node.children:
                node.children[c] = Node()
               
            node = node.children[c]
            i += 1
       
        node.end = True

    def search(self, word: str) -> bool:
        node = self.searchEndNode(word)
        return node and node.end

    def startsWith(self, prefix: str) -> bool:
        return self.searchEndNode(prefix) is not None
   
    def searchEndNode(self, word):
        i = 0
        n = len(word)
        node = self.root
        while i < n:
            c = word[i]
           
            if c not in node.children:
                return None
               
            node = node.children[c]
            i += 1
       
        return node
       
class Node:
    def __init__(self):
        self.children = {}
        self.end = False
Click to expand...
bai dang nay cung chua tung giai qua, nhung nhin thay mot so tinh chat cua 2 kieu order traversal nay
postOrder -> root nam cuoi (xac dinh dc root value)
inOrder -> ben trai cua root la left subtree, ben phai la right subtree
Nhung neu de cho root val k co unique thi co ve kha hack nao
 
nay viết TS mà type nó loạn xì ngậu thôi chuyển về JS viết cho dễ kk
JavaScript: 
class Trie {
  constructor() {
    this.root = new Map();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.has(char)) node.set(char, new Map());
      node = node.get(char);
    }
    node.set('word', true);
  }

  traverse(word) {
    let node = this.root;
    for (const char of word) {
      node = node.get(char);
      if (node == null) return null;
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return node != null && node.get('word') === true;
  }

  startsWith(prefix) {
    return this.traverse(prefix) != null;
  }
}
 
NahSama said:
bai dang nay cung chua tung giai qua, nhung nhin thay mot so tinh chat cua 2 kieu order traversal nay
postOrder -> root nam cuoi (xac dinh dc root value)
inOrder -> ben trai cua root la left subtree, ben phai la right subtree
Nhung neu de cho root val k co unique thi co ve kha hack nao
Click to expand...
đề nó bắt buộc phải unique đó, ví dụ có 2 root giống nhau thì ở bên inorder sẽ tách thành 2 kiểu tree khác nhau.
 
Code: 
class Trie {
    class TrieNode {
        public TrieNode[] kids;
        public boolean isWord;
       
        public TrieNode() {
            this.kids = new TrieNode[26];
            this.isWord = false;
        }

        public void add(String s) {
            char[] c = s.toCharArray();
            TrieNode cur = this;
            for(int i = 0; i < c.length; i++){
                char ch = c[i];
                if (cur.kids[ch - 'a'] == null) {
                    cur.kids[ch - 'a'] = new TrieNode();
                }

                cur = cur.kids[ch - 'a'];
                if (i == c.length - 1) {
                    cur.isWord = true;
                }
            }
        }
    }

    TrieNode trie;

    public Trie() {
        this.trie = new TrieNode();
    }
   
    public void insert(String word) {
        trie.add(word);
    }
   
    public boolean search(String word) {
        TrieNode cur = this.trie;
        char[] c = word.toCharArray();
        for(int i = 0; i < c.length; i++){
            char ch = c[i];
            if (cur.kids[ch - 'a'] == null) return false;
            cur = cur.kids[ch - 'a'];
        }
        return cur.isWord;
    }
   
    public boolean startsWith(String prefix) {
        TrieNode cur = this.trie;
        char[] c = prefix.toCharArray();
        for(int i = 0; i < c.length; i++){
            char ch = c[i];
            if (cur.kids[ch - 'a'] == null) return false;
            cur = cur.kids[ch - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
 
Đảng viên Hanni said:
@chiyeuemthoi Nộp bài thử nào bạng.
iErjo0A.png

C++: 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define i64 long long
typedef vector<i64> vi;
typedef pair<i64,i64> pii;
typedef double ld;
typedef unsigned long long ull;
typedef tree<i64, null_type, less_equal<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main(){
    faster();
    int t;
    cin>>t;
    while(t--){
        int n, ins, del, cop;
        cin>>n>>ins>>del>>cop;
        int dp[n+1];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=min(dp[i-1]+ins,(i%2==0?dp[i/2]+cop:dp[(i+1)/2]+cop+del));
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}
Click to expand...
chiyeuemthoi said:
sai fen ạ
Click to expand...
hình như xai là do chạy từ i = 1, dp[(1+1)/2] == dp[1] chưa khởi tạo ko biết int dp[n+1]; nó có khởi tạo dp[1] = 0 hay ko. Nếu nó khởi tạo dp chứa giá trị = 0 hết thì có nguy cơ dp[1] = min(dp[0] + X, dp[1] + Z + Y) = min(X, Z+Y) có khi nó = Z+Y, xai vì dp[1] luôn = X mới đúng. Nếu nó ko khởi tạo giá trị nào thì đọc giá trị dp[1] là undefined behavior
kH9BFd2.gif

sửa lại:
C++: 
#include <iostream>
#include <vector>

int findTotalTime_dp(int N, int X, int Y, int Z) {
    std::vector<int> dp(N + 1);
    dp[1] = X;
    for (int i = 2; i <= N; ++i) dp[i] = std::min(dp[i - 1] + X, dp[(i + 1) / 2] + Z + i % 2 * Y);
    return dp[N];
}

int main() {
    int T, N, X, Y, Z;
    std::cin >> T;
    while (std::cin >> N >> X >> Y >> Z) std::cout << findTotalTime_dp(N, X, Y, Z) << "\n";
}
nộp coi đúng ko
1BW9Wj4.png
toy test XYZ từ 1 tới 40 thấy đúng hết với N=100 và N=77
DP 5 dòng bỏ dòng dp[0] = 0 nữa thì còn 4 dòng
WurVrha.png

Dijkstra code gần 20 dòng dùng dao giết trâu mổ gà nhưng ít phải rặn não như cái dp này
JiZo9zf.png
toy đâu có nghĩ ra được cái đổi cái -1 kia thành x2 rồi mới -1 đâu
OANgL56.png
 
Last edited:
Spaghetti Code said:
hình như xai là do chạy từ i = 1, dp[(1+1)/2] == dp[1] chưa khởi tạo ko biết int dp[n+1]; nó có khởi tạo dp[1] = 0 hay ko. Nếu nó khởi tạo dp chứa giá trị = 0 hết thì có nguy cơ dp[1] = min(dp[0] + X, dp[1] + Z + Y) = min(X, Z+Y) có khi nó = Z+Y, xai vì dp[1] luôn = X mới đúng. Nếu nó ko khởi tạo giá trị nào thì đọc giá trị dp[1] là undefined behavior
kH9BFd2.gif

sửa lại:
C++: 
#include <iostream>
#include <vector>

int findTotalTime_dp(int N, int X, int Y, int Z) {
    std::vector<int> dp(N + 1);
    dp[1] = X;
    for (int i = 2; i <= N; ++i) dp[i] = std::min(dp[i - 1] + X, dp[(i + 1) / 2] + Z + i % 2 * Y);
    return dp[N];
}

int main() {
    int T, N, X, Y, Z;
    std::cin >> T;
    while (std::cin >> N >> X >> Y >> Z) std::cout << findTotalTime_dp(N, X, Y, Z) << "\n";
}
nộp coi đúng ko
1BW9Wj4.png
toy test XYZ từ 1 tới 40 thấy đúng hết với N=100 và N=77
DP 5 dòng bỏ dòng dp[0] = 0 nữa thì còn 4 dòng
WurVrha.png

Dijkstra code gần 20 dòng dùng dao giết trâu mổ gà nhưng ít phải rặn não như cái dp này
JiZo9zf.png
toy đâu có nghĩ ra được cái đổi cái -1 kia thành x2 rồi mới -1 đâu
OANgL56.png
Click to expand...
cái này dp với dijkstra em thấy cũng time luôn , nma thấy dp ngắn hơn
JGdqgzY.png

1679022884484.png
 
JavaScript: 
class Trie {
    constructor() {
        this.root = {};
    }

    insert(word) {
        let node = this.root;
        for (const ch of word) {
            node[ch] ??= {};
            node = node[ch];
        }
        node.$ = true;
    }

    #nodeAt(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node[ch]) {
                return false;
            }
            node = node[ch];
        }

        return node;
    }

    search(word) {
        return this.#nodeAt(word)?.$ === true;
    }

    startsWith(word) {
        return !!this.#nodeAt(word);
    }
}
 
dtsT9bj.png
Đúng ra là dùng Array mà thôi, HashMap cho nhẹ đầu
s360TUU.png


Java: 
class Trie {
    private Node root;
    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node ptr = root;
        for(int i = 0; i < word.length(); i++){
            char curr = word.charAt(i);
            if(!ptr.dict.containsKey(curr)){
                ptr.dict.put(curr, new Node());
            }
            ptr = ptr.dict.get(curr);
        }
        ptr.isEnd = true;
    }
    
    public boolean search(String word) {
        Node ptr = root;
        for(int i = 0; i < word.length(); i++){
            char curr = word.charAt(i);
            if(ptr.dict.containsKey(curr)){
                ptr = ptr.dict.get(curr);
            }
            else{
                return false;
            }
        }
        return (ptr.isEnd);
    }
    
    public boolean startsWith(String prefix) {
        Node ptr = root;
        for(int i = 0; i < prefix.length(); i++){
            char curr = prefix.charAt(i);
            if(ptr.dict.containsKey(curr)){
                ptr = ptr.dict.get(curr);
            }
            else{
                return false;
            }
        }
        return true;
    }
}
class Node {
    public HashMap<Character, Node> dict;
    public boolean isEnd;
    public Node(){
        dict = new HashMap<>();
        isEnd = false;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
 
Spaghetti Code said:
hình như xai là do chạy từ i = 1, dp[(1+1)/2] == dp[1] chưa khởi tạo ko biết int dp[n+1]; nó có khởi tạo dp[1] = 0 hay ko. Nếu nó khởi tạo dp chứa giá trị = 0 hết thì có nguy cơ dp[1] = min(dp[0] + X, dp[1] + Z + Y) = min(X, Z+Y) có khi nó = Z+Y, xai vì dp[1] luôn = X mới đúng. Nếu nó ko khởi tạo giá trị nào thì đọc giá trị dp[1] là undefined behavior
kH9BFd2.gif

sửa lại:
C++: 
#include <iostream>
#include <vector>

int findTotalTime_dp(int N, int X, int Y, int Z) {
    std::vector<int> dp(N + 1);
    dp[1] = X;
    for (int i = 2; i <= N; ++i) dp[i] = std::min(dp[i - 1] + X, dp[(i + 1) / 2] + Z + i % 2 * Y);
    return dp[N];
}

int main() {
    int T, N, X, Y, Z;
    std::cin >> T;
    while (std::cin >> N >> X >> Y >> Z) std::cout << findTotalTime_dp(N, X, Y, Z) << "\n";
}
nộp coi đúng ko
1BW9Wj4.png
toy test XYZ từ 1 tới 40 thấy đúng hết với N=100 và N=77
DP 5 dòng bỏ dòng dp[0] = 0 nữa thì còn 4 dòng
WurVrha.png

Dijkstra code gần 20 dòng dùng dao giết trâu mổ gà nhưng ít phải rặn não như cái dp này
JiZo9zf.png
toy đâu có nghĩ ra được cái đổi cái -1 kia thành x2 rồi mới -1 đâu
OANgL56.png
Click to expand...
Keg787O.png
đúng rồi, em sai ở đó, bác có tâm phết, em gõ mấy dòng còn lười test.
rPqev6F.png
 

Similar threads

nhbin
kiến thức Kèo Watch to earn 5p mỗi ngày $EVERY gọi vốn $60M từ A16Z, Coinbase, DragonFly
Replies
0
Views
102
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
638
heocon0123
heocon0123
MasterchiefsReborn
Sinh viên than kiến tập mà làm việc không kịp ăn
2 3
Replies
47
Views
3K
OneThing
OneThing
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
164
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
17
Views
445
truonggiang!
T

Share this page

Back
Top