P1064 [NOIP 2006 提高組] 金明的預算方案
背包＋附屬品DP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, v, p, q;
struct node{int id, v, s, f;
}a[100];
int b[32010], dp[32010];
bool cmp(node a, node b){if(a.id == b.id)return a.f < b.f;return a.id < b.id;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++){cin >> v >> p >> q;if(q == 0)a[i].id = i, a[i].v = v, a[i].f = 0, a[i].s = v * p;else a[i].id = q, a[i].v = v, a[i].f = ++b[q], a[i].s = v * p;}sort(a + 1, a + m + 1, cmp);for(int i = 1; i <= m; i++){if(a[i].f)continue;for(int j = n; j >= a[i].v; j--){dp[j] = max(dp[j], dp[j - a[i].v] + a[i].s);if(a[i].id == a[i + 1].id && j >= a[i].v + a[i + 1].v){dp[j] = max(dp[j], dp[j - a[i].v - a[i + 1].v] + a[i].s + a[i + 1].s);}if(a[i].id == a[i + 2].id && j >= a[i].v + a[i + 2].v){dp[j] = max(dp[j], dp[j - a[i].v - a[i + 2].v] + a[i].s + a[i + 2].s);}if(a[i].id == a[i + 2].id && j >= a[i].v + a[i + 1].v + a[i + 2].v){dp[j] = max(dp[j], dp[j - a[i].v - a[i + 1].v - a[i + 2].v] + a[i].s + a[i + 1].s + a[i + 2].s);}}}cout << dp[n] << endl;return 0;
}P1156 垃圾陷阱
做法一：DFS
#include<bits/stdc++.h>
using namespace std;
#define int long long
int d, n;
struct node{int t, f, h;
}a[105];
bool cmp(node a, node b){return a.t < b.t;
}
int ans1 = 1e9, ans2;
void dfs(int t, int h, int pos){if(h >= d){ans1 = min(ans1, a[pos - 1].t);return;}if(a[pos].t > t || pos > n){ans2 = max(ans2, t);return;}dfs(t, h + a[pos].h, pos + 1);dfs(t + a[pos].f, h, pos + 1);
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> d >> n;for(int i = 1; i <= n; i++)cin >> a[i].t >> a[i].f >> a[i].h;sort(a + 1, a + n + 1, cmp);dfs(10, 0, 1);if(ans1 == 1e9)cout << ans2 << endl;else cout << ans1 << endl;return 0;
}記憶化改進
#include<bits/stdc++.h>
using namespace std;
#define int long long
int d, n;
struct node{int t, f, h;
}a[105];
bool cmp(node a, node b){return a.t < b.t;
}
int ans1 = 1e9, ans2;
bool dp[1010][110][110];
void dfs(int t, int h, int pos){if(h >= d){ans1 = min(ans1, a[pos - 1].t);return;}if(a[pos].t > t || pos > n){ans2 = max(ans2, t);return;}if(dp[t][h][pos])return;dp[t][h][pos] = 1;dfs(t, h + a[pos].h, pos + 1);dfs(t + a[pos].f, h, pos + 1);
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> d >> n;for(int i = 1; i <= n; i++)cin >> a[i].t >> a[i].f >> a[i].h;sort(a + 1, a + n + 1, cmp);dfs(10, 0, 1);if(ans1 == 1e9)cout << ans2 << endl;else cout << ans1 << endl;return 0;
}mp改進
#include<bits/stdc++.h>
using namespace std;
#define int long long
int d, n;
struct node{int t, f, h;
}a[105];
bool cmp(node a, node b){return a.t < b.t;
}
int ans1 = 1e9, ans2;
map<int, map<int, map<int, bool> > >dp;
void dfs(int t, int h, int pos){if(h >= d){ans1 = min(ans1, a[pos - 1].t);return;}if(a[pos].t > t || pos > n){ans2 = max(ans2, t);return;}if(dp[t][h][pos])return;dp[t][h][pos] = 1;dfs(t, h + a[pos].h, pos + 1);dfs(t + a[pos].f, h, pos + 1);
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> d >> n;for(int i = 1; i <= n; i++)cin >> a[i].t >> a[i].f >> a[i].h;sort(a + 1, a + n + 1, cmp);dfs(10, 0, 1);if(ans1 == 1e9)cout << ans2 << endl;else cout << ans1 << endl;return 0;
}
