做网站如何找项目,江西省飞宏建设工程有限公司 网站,规划设计网站推荐,ppt模板免费下载 素材千图网K soyorin的通知
完全背包加不少于的模型
由于人数只有1000#xff0c;那么 bi 实际有效的范围只有1000左右#xff0c;并且#xff0c;soyorin至少要花一次 p 的代价将消息通知给 1 个人#xff0c;然后再让这个人去将消息通知给剩下的 n−1 个人。
那么问题就转化…K soyorin的通知
完全背包加不少于的模型
由于人数只有1000那么 bi 实际有效的范围只有1000左右并且soyorin至少要花一次 p 的代价将消息通知给 1 个人然后再让这个人去将消息通知给剩下的 n−1 个人。
那么问题就转化成了将消息通知给 n−1 个人的最小代价将消息通知给 bi 个人需要花费 ai 的代价且 ai,bi 能用多次也就是一个完全背包。
注意一些细节
#include bits/stdc.h
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl \n
#define lowbit(x) x (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pairint, int PII;
typedef pairdouble, double PDD;
#define LF(x) fixed setprecision(x)
#define max(a, b) (((a) (b)) ? (a) : (b))
#define min(a, b) (((a) (b)) ? (a) : (b))
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N 1e6 10, M 1010, inf 0x3f3f3f3f, mod 1e9 7, P 13331;
const double eps 1e-8;
int f[N];
void solve()
{int n, p;cin n p;memset(f, 0x3f, sizeof f);f[0] 0;for (int i 1; i n; i){int a, b;cin a b;if (b n)b n - 1; // b可能会大于你但是必须选择一个别人故最多n-1个for (int j 0; j n; j) // 这一步从0开始枚举其实就是f[i][j]表示前i个选人数不小于j的最少花费f[j] min(f[j], f[max(0, j - b)] a);}int ans 1e9;for (int i 0; i n; i)ans min(ans, f[i] (n - i) * p);cout ans endl;
}
signed main()
{Yshanqian;int T;T 1;// cin T;for (int cases 1; cases T; cases){// coutCase #cases: ;solve();}return 0;
}
