自用算法笔记(持续更新)

#include
using namespace std;
int a[100010];
int t[100010];
/*void merge_sort(int a[],int l,int r){
    if(l == r)return;
    int mid = l + r >> 1;
    merge_sort(a,l,mid),merge_sort(a,mid+1,r);
    for(int i = l,j = l, k = mid + 1; i <= r; i ++){
        if(j == mid + 1) 
            t[i] = a[k ++];
        else if(k == r + 1)
            t[i] = a[j ++];
        else t[i] = a[j] < a[k] ? a[j ++] : a[k ++];
    }
    for(int i = l; i = r) return;

    //寻找数组中点下标
    int mid = (l+r)>>1;
    //递归给左半边排序
    merge_sort(a,l,mid);
    //递归给右半边排序
    merge_sort(a,mid+1,r);
    //以下是合并排序好的两个数组

    //k：遍历合并后的数组的下标
    int k = 0;
    //i:左半边数组的下标，j:右半边数组的下标
    int i = l, j = mid + 1;
    //左右半边都没遍历完
    while(i <= mid && j <= r){
        //左边的元素小于右边的元素
        if(a[i] < a[j]) 
            //左边元素放如临时数组，并移动下标
            temp[k++] = a[i++];
        //否则，右边元素放入临时数组并移动下标 
        else temp[k++] = a[j++];
    }
    //如果左边数组有剩余，则放入临时数组
    while(i <= mid) temp[k++] = a[i++];
    //如果有边数组有剩余，则放入临时数组
    while(j <= r) temp[k++] = a[j++];
    //把临时数组中的元素拷贝至原数组
    k = 0;
    for(int i = l; i <= r; i++){
        a[i] = temp[k++];
    }

}


int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n; i ++){
        scanf("%d",&a[i]);
    }
    merge_sort(a,0,n-1);
    for(int i = 0 ; i < n; i ++){
        printf("%d ",a[i]);
    }
}

没有单调性也可能二分（本质不是单调性）

整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l > 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l > 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

#include
using namespace std;
stack st;
int n;
int main(){
	cin >> n;
	long long ans= 0; 
	long long cnt = 0;
	for(int i = 1 ; i > x;	
		while(!st.empty()&&st.top()<=x){
				st.pop();
				cnt--; 
			}
			ans+=cnt;
			st.push(x);
			cnt++;
		}
	}
	cout << ans;
	return 0;
}

#include
using namespace std;
const int N = 2e6 + 10;
struct node{int v,id;}a[N];
deque q;
int n,k;
int main(){
	cin >> n >>k;
	for(int i= 1; i > a[i].v;
		a[i].id = i;
	}
	for(int i = 1; i <= n; i ++){
		while(!q.empty()&&q.back().v=k)cout << q.front().v<<endl;
	}
	return 0;
}

#include

using namespace std;

const int N=100009;

int a[N],tr[N];

int n,m;

//每个数的间隔，背下来就行
int lowbit(int x)
{
    return x&-x;
}

//第x个数加上v
int add(int x,int v)
{
    //因为树状数组的性质，加一个数，只影响logn个数，所有不用全加完
    //从当前位置开始加，每个间隔是lowbit(i)，一直加到最后
    for(int i=x;i>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        add(i,a[i]);//第i个数加上a[i]

while(m--)
{
    int k,x,y;
    scanf("%d%d%d",&k,&x,&y);
    if(k==0) printf("%d\n",qurry(y)-qurry(x-1));
    else add(x,y);
}
return 0;

}

#include
#include
#include
#include

using namespace std;

const int N=100010;

int n,m;

int w[N];//记录一下权重

struct node{
    int l,r;//左右区间

    int sum;//总和
}tr[N*4];//记得开 4 倍空间 


void push_up(int u)//利用它的两个儿子来算一下它的当前节点信息
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//左儿子 u<<1 ,右儿子 u<>1;//边界的话直接去计算一下 l + r 的下取整

        build(u<<1,l,mid);//先递归一下左儿子

        build(u<<1|1,mid+1,r);//然后递归一下右儿子

        push_up(u);//做完两个儿子之后的话呢 push_up 一遍u 啊，更新一下当前节点信息
    }
}

int query(int u,int l,int r)//查询的过程是从根结点开始往下找对应的一个区间
{
    if(l<=tr[u].l&&tr[u].r>1;//计算一下我们 当前 区间的中点是多少
    //先判断一下和左边有没有交集

    int sum=0;//用 sum 来表示一下我们的总和

    if(mid>=l)sum+=query(u<=mid+1)//看一下我们当前区间的中点和右边有没有交集
    sum+=query(u<>1;
      //看一下 x 是在左半边还是在右半边
      if(x<=mid)modify(u<<1,x,v);//如果是在左半边，那就找左儿子
      else modify(u<<1|1,x,v);//如果在右半边，那就找右儿子

      //更新完之后当前节点的信息就要发生变化对吧，那么我们就需要 pushup 一遍

      push_up(u);
    }

}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    build(1,1,n);/*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */

    //后面的话就是一些修改操作了

    while(m--)
    {
        int k,a,b;

        scanf("%d%d%d",&k,&a,&b);

        if(!k)printf("%d\n",query(1,a,b));//求和的时候，也是传三个参数，第一个的话是根节点的编号 ，第二个的话是我们查询的区间 
        //第一个参数也就是当前节点的编号
        else
        modify(1,a,b);//第一个参数是根节点的下标,第二个参数是要修改的位置，第三个参数是要修改的值

    }


    return 0;
}

作者：Elegant
链接：https://www.acwing.com/solution/content/40394/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include
using namespace std;
const int N = 5e5 + 10;
int a[N];
int b[N];
int tr[N];
int n,m;
int lowbit(int x){
	return x & -x;
}
void add(int k,int c){
	for(int i = k; i  0; i -= lowbit(i)){
		res += tr[i];
	}	
	return res;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i > a[i];
		b[i] = a[i] - a[i - 1];
		add(i,b[i]);
	}
	while(m --){
		int op;
		cin >> op;
		if(op == 1){
			int x,y,k;
			cin >> x >> y >> k;
			add(x,k);
			add(y + 1,-k);
		}else{
			int x;
			cin >> x;
			cout << query(x) << endl;
		}
	}
}

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 100010;

std::vector G[MAXN];
int n, m;
bool visited[MAXN];
queue q;

void dfs(int x, int cur) {//x指当前所在的节点，cur指已遍历过的节点个数
	visited[x] = true;//标记以避免重复访问
	cout << x << " ";//输出
	if (cur == n) return ;
	for (int i=0; i<G[x].size(); i++)
		if (!visited[G[x][i]]) dfs(G[x][i], cur+1);//记得要判断是否遍历过
}

void bfs(int x) {
	memset(visited, false, sizeof(visited));//记得一定要清空
	visited[x] = true;
	q.push(x);
	while (!q.empty()) {
		int v = q.front();
		q.pop();//记得要弹出，否则会一直在第一层遍历
		cout << v << " ";//输出
		for (int i=0; i> n >> m;
	for (int i=1; i> u >> v;
		G[u].push_back(v);//标准邻接表建有向图
	}
	for (int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());//标准vector排序
	dfs(1, 0);
	cout << endl;
	bfs(1);
	cout << endl;
	return 0;//完结撒花！
}

由中序和前序求后序
#include
using namespace std;
string pre,inor;
void dfs(string pre,string inor){
    if(pre.empty())return;
    char root = pre[0];
    int k = inor.find(root);
    pre.erase(pre.begin());
    string leftpre = pre.substr(0,k);
    string rightpre = pre.substr(k);
    string leftinor = inor.substr(0,k);
    string rightinor = inor.substr(k + 1);
    dfs(leftpre,leftinor);
    dfs(rightpre,rightinor);
    printf("%c",root);

}
int main(){
    cin >> inor >>pre ;
    dfs(pre,inor);
    putchar('\n');
    return 0;
}

由中序和后序求前序
#include
using namespace std;
string inor,post;
void solve(string inor,string post){
    if(post.empty())return;
    char root = post[post.size() - 1];
    post.erase(post.end()-1);
    int k = inor.find(root);
    
    string inorleft = inor.substr(0,k);
    string inorright= inor.substr(k + 1);
    string postleft = post.substr(0,k);
    string postright = post.substr(k);
    cout <> inor >> post;
    solve(inor,post);
    return 0;
}

#include
#include
#include
#include
using namespace std;
string pre,inor;
void work(string pre,string inor)
{
    if(pre.empty())return;
    //如果序列空了，就没必要继续了
    char root=pre[0];
    //取到前序序列的首字母，即根节点
    int k=inor.find(root);
    //找到中序序列中根节点的位置
    pre.erase(pre.begin());
    //删去前序序列中的根节点
    string leftpre=pre.substr(0,k);
    //从0开始切割k个
    string rightpre=pre.substr(k);
    //从k开始切割到最后
    string leftinor=inor.substr(0,k);
    //从0开始切割k个
    string rightinor=inor.substr(k+1);
    //从k+1开始切割到最后
    work(leftpre,leftinor);
    work(rightpre,rightinor);
    printf("%c",root);
    //因为要输出后序序列，所以是左右根
    //先遍历左子树，再右子树，再根节点
}
int main()
{
    cin>>inor>>pre;
    work(pre,inor);
    putchar('\n');
    return 0;
}

#include
using namespace std;
const int N = 1e5 + 10;
vector G[N];//邻接表 
queue q;//队列操作 
int d[N];//统计入度 
int n,m,cnt,ans[N];//ans数组记录答案 
int main(){
	cin >> n >> m;
	for(int i = 1 ;i > x>> y;
		G[x].push_back(y);
		d[y]++;//统计入度 
	}
	for(int i =1; i <= n; i ++){
		if(d[i]==0)q.push(i);//1
	}
	while(q.size()){
		int t = q.front();
		q.pop();
		ans[cnt++] = t;
		for(int i = 0 ; i < G[t].size();i  ++){
			d[G[t][i]]--;//删边操作 
			if(d[G[t][i]]==0) q.push(G[t][i]);//删完后入度为0的话，放入队列 
		}
	}
	if(cnt == n)for(int i = 0; i <cnt; i ++)cout << ans[i]<<" ";
	else cout <<-1;
	return 0;
}

/**
	每个任务前的耗时最长的任务相加即为答案，详情看洛谷深入浅出
**/
#include 
#include 
#include 

using namespace std;

const int N = 500005;

int ind[N], f[N], a[N];  // ind--入度   f--答案   a--时间
vector edge[N];
queue q;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i > x;
        cin >> a[i];
        while (true) {
            int y;
            cin >> y;
            if (y == 0)
                break;
            edge[y].push_back(x);
            ind[x]++;
        }
    }
    // 步骤一
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
            f[i] = a[i];
        }
    };
    while (!q.empty()) {
        int rhs = q.front();
        q.pop();
        // 步骤二
        for (int i = 0; i < edge[rhs].size(); i++) {
            int u = edge[rhs][i];
            ind[u]--;
            if (ind[u] == 0)
                q.push(u);  // 步骤三
            f[u] = max(f[u], f[rhs] + a[u]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[i]);   // 统计答案
    }
    cout << ans << endl;
    return 0;
}

/**
	先找出所有入度为0的，初始链数为1，后面搜到的每个点，都等于各个点链数之和，详情看洛谷深入浅出
**/
#include
using namespace std;
const int N = 5e3 + 10;
int ans[N],outd[N],ind[N];
vectorG[N];
queueq;
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0; i > x >> y;
        ind[y]++;
        outd[x]++;
        G[x].push_back(y);
    }
    for(int i = 1; i <= n; i ++){
        if(ind[i]==0){
            q.push(i);  
			ans[i] = 1; 
        }

}
while(q.size()){
    auto t = q.front();
    q.pop();
    for(int i = 0 ; i < G[t].size(); i ++){
        int x = G[t][i];
        ind[x] --;
		if(ind[x]==0){
            q.push(x);
        }
        ans[x] = (ans[x] + ans[t])%80112002;
    }
}
int res = 0;
for(int i = 1; i <= n; i ++){
    if(outd[i]==0){
        res= (res + ans[i])%80112002;
    }
}
cout << res;
return 0;

}

#include
#include
#include
using namespace std;

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大

dist[1]=0;  //第一个点到自身的距离为0

for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
{
    int t=-1;       //t存储当前访问的点

    for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
        if(!st[j]&&(t==-1||dist[j]<dist[t]))     
            t=j;

    st[t]=true;   

    for(int j=1;j>n>>m;

memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
                            //所以每个点初始为无限大

while(m--)
{
    int x,y,z;
    cin>>x>>y>>z;
    g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
}

cout<<Dijkstra()<<endl;
return 0;

}

/**
	邻接表存的话不用考虑重边，dij算法会取最小的
**/
#include
using namespace std;
typedef pairPII;
const int N = 1e5 + 10;
// 稀疏图用邻接表来存
vector<vector>G;
int dist[N];
bool st[N];
int n,m;
int dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;
	// 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    // 这个顺序不能倒，pair排序时是先根据first，再根据second，
     // 这里显然要根据距离排序,对pair排序默认先对first,所以first放距离更省事 
    priority_queue<PII,vector,greater>heap;
	heap.push({0,1});
	while(heap.size()){
		auto t = heap.top();
		heap.pop();
		int distance = t.first,node = t.second;
		if(st[node])continue;
		st[node] = true;
	
		for(int i = 0; i dist[node] + len){
				dist[newNode] = dist[node] + len;
				heap.push({dist[newNode],newNode});
			}
		}
	}
	if(dist[n] == 0x3f3f3f3f)return -1;
	else return dist[n];
}
int main(){
	cin >> n >> m;
	G.resize(n + 1);
	for(int i = 0; i > x >> y >> z;
		G[x].push_back({y,z});
	}
	cout << dijkstra();
	return 0;
}

#include
using namespace std;
int G[510][510];
int dist[510];
int num[510];//救援队
int n,m,c1,c2;
bool vis[510];
int weight[510];
int num2[510];//最短路数量
void dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[c1] = 0;
    num2[c1] = 1;
    num[c1] = weight[c1];
    for(int i = 0; i < n ; i ++){
        int t = -1;
        for(int j = 0; j dist[j])){
                t = j;
            }
        }
        vis[t] = true;
        for(int j = 0; j < n; j ++){
            // dist[j] = min(dist[j],dist[t] + G[t][j]);
            if(dist[t] + G[t][j]  num[j])
            num[j] = num[t] + weight[j];
                
                

        }
    }
}
cout << num2[c2] <<" "<>n >> m >>c1>>c2;
    for(int i = 0; i > weight[i];
    }
    memset(G,0x3f,sizeof G);
    while(m --){
        int x,y,z;
        cin >> x >> y >> z;
        G[x][y] = min(G[x][y],z);
        G[y][x] = min(G[y][x],z);
        // G[x][y] = G[y][x]= z;
    }
    dijkstra();
    return 0;
}

void DFS(int s,int v){ //s是起点编号，v是当前访问的顶点编号(从终点开始递归)
	if(v == s){
        printf("%d\n",s);
        return ;
    }
    DFS(s,pre[v]);
    printf("%d\n",v);
}

#include
using namespace std;
//交换律 结合律 把偶数的先结合成0，最后只剩落单的和0异或还是它自己
int ans,n,a;//ans是所有数异或之后的结果，也就是题目所求的落单的筷子的数目

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
   	  	scanf("%d",&a);
		ans^=a;//把所有的数都异或起来
	}
	printf("%d",ans);
	return 0;
}

#include
using namespace std;
long long c[2010][2010];
int main(){
	int t,k,m,n;
	cin >> t >> k;
	//先设置一个杨辉三角
    for(int i = 0; i <= 2000; i ++){
		c[i][0] = c[i][i] = 1;
		for(int j= 1; j > n >> m;
			for(int i = 0; i <= n; i ++)
				for(int j = 0; j <= min(i,m); j ++)
					ans+=c[i][j] == 0;
		
			cout << ans << endl;
		}	
		return 0;
}

void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}

#include 
#include 

using namespace std;

const int N = 1000010;

//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i 0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] > n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

#include
using namespace std;
int n;
long long int qmi(long long int base, long long int power, long long int p)
{
	long long int result = 1;   
	while (power > 0)           
	{
		if (power & 1)         							
			result = result * base % p;   
			//根据公式每个项都取余数后在再做累乘
		base = base * base % p ;   
			//根据公式每个项都取余数后在再做平方操作      						
		power >>= 1;         						
	}
			//根据公式在最后的的结果上再来一次取余数
	return result % p;       
}
int main(){
    cin >> n;
    while(n --){
        int base,power,p;
        cin >> base >> power >> p;
        cout << qmi(base,power,p)<<endl;
    }
    return 0;
}

#include

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i > v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

for(int i = 1; i = 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 优化前
            f[j] = f[j];            // 优化后，该行自动成立，可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后

#include
using namespace std;
const int P = 1e3 + 10;
int N,V;
int v[P],w[P];
int mm[P][P];
// int dfs(int x,int spV){
//     if(x > N || spV < 0)mm[x][spV] = 0;
//     else if(spV > N >> V;
    for(int i = 1; i > v[i] >> w[i];
    }
    // int res = dfs(1,V);
    for(int i = 1; i <= N; i ++){
        for(int j = 1; j <= V; j ++){
            if(j < v[i])mm[i][j] = mm[i - 1][j];
    else mm[i][j] = max(mm[i - 1][j],mm[i][j - v[i]]+ w[i]);
        }
    }
    cout << mm[N][V];
    return 0;
}

//二维正序枚举，下面的写法不舒服，可以把上面的改成正序的
#include
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i >v[i]>>w[i];
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = 0 ; j<=m ;j++)
    {
        for(int k = 0 ; k*v[i]<=j ; k++)
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    }

    cout<<f[n][m]<<endl;
}

#include
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i >v[i]>>w[i];
    }

for(int i = 1 ; i<=n ;i++)
    //j小于v[i]的不改变
for(int j = v[i] ; j<=m ;j++)
{
        f[j] = max(f[j],f[j-v[i]]+w[i]);
}
	cout<<f[m]<<endl;

}

#include 
#include 

using namespace std;
const int N = 110;

int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i > v[i] >> w[i] >> s[i];

for(int i = 1; i <= n; i ++){//枚举背包
    for(int j = 1; j <= m; j ++){//枚举体积
        //k从0开始，可能一个都不选
        for(int k = 0; k =  k * v[i]){
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
}

cout << f[n][m] << endl;

return 0;

}

#include
using namespace std;

const int N=110;
int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=1;i>s[i];
        for(int j=0;j>v[i][j]>>w[i][j];  //读入
        }
    }

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        f[i][j]=f[i-1][j];  //不选
        for(int k=0;k=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
        }
    }
}
cout<<f[n][m]<<endl;
}

因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积
#include
using namespace std;

const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=0;i>s[i];
        for(int j=0;j>v[i][j]>>w[i][j];
        }
    }

for(int i=0;i=0;j--){
        for(int k=0;k=1;k--)也可以
            if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
        }
    }
}
cout<<f[m]<<endl;

}

#include
using namespace std;
const int N = 1e4 + 10;
int n,m;
int a[N];
int f[N][N];
/*int dfs(int u,int spSum){
	if(f[u][spSum]!=0)return f[u][spSum];
	else if(spSum != 0 && u > n)f[u][spSum] = 0;
	else if(spSum > n >>m;
	for(int i = 1; i > a[i];
	}
    
	for (int i = 0; i = 1; i--) {
        for (int j = 1; j = a[i]) {
                f[i][j] += f[i + 1][j - a[i]];  // 选择第i个数
            }
        }
    }
    cout << f[1][m];
	return 0;
}

#include 
#include 

using namespace std;

const int N = 1005;

int n, m;
int v[N], w[N];
int f[N][N]; 

int main() {
    cin >> n >> m;
    
    for (int i = 1; i > v[i] >> w[i];
    
    for (int i = n; i >= 1; --i) 
        for (int j = 0; j = v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    
    // 在此，f[1][m]就是最大数量
    int j = m;
    for (int i = 1; i = v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    return 0;
}

这是一道变了形的01背包

首先我们因为和每个人打都一定有经验所以一定都要打一遍。

所以不难想到max=lose[1]+lose[2]......+lose[n]+某些磕了药打赢的多出的经验值

因此我们可以进行一个转换，把价值记为win[i]-lose[i]，溶剂就是要打赢磕的药，然后要使价值总和最大，然后就变成了基础的零一背包了。。。

#include
#include
#include
#include
#include
#include
using namespace std;
int a[100005];
long long f[1000005];
int win[100005];
int v[100005];
int lose[100005];
int main()
{
    int n,m;
    int sum=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&lose[i],&win[i],&v[i]);
        a[i]=win[i]-lose[i];
        sum=sum+lose[i];
    }
    for (int i=1;i=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+a[i]);
        }
    }
    printf("%lld",5*(f[m]+sum));
    return 0;
}