矩阵消除游戏
矩阵消除游戏
首先用n位二进制表示n行里面哪些行是被挑走了，哪些是留着的，对这个二进制遍历，九八所有n行的可能结果就遍历出来，然后去把每一情况下的剩下的列的和从大到小排列，然后就先看行呗挑走的数量，然后k-这个数就是lie的数量，从大到小贪心吃这个数量。即可，注意特殊情况判断（k>=m||k>=n).然后直接用数组需要每次挑行的时候都重新赋值为0，不然会出问题，vector也一样用fill重新赋值。
//vector版
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long ll;
//int sm[N],ps[N];
int n,m,k,cnt;
vector<vector<int>> v(20,vector<int>(20));
vector<int>lie(20,0);
bool cmp(int a,int b)
{return a>b;
}
int calc(int x)
{int sum2=0;for(int i=1;i<=n;i++){if(((x>>(i-1))&1)==1){for(int j=1;j<=m;j++){sum2+=v[i][j];}cnt++;}else {for(int j=1;j<=m;j++){lie[j]+=v[i][j];}}}return sum2;
}
void solve() {cin>>n>>m>>k;int sum1=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>v[i][j];sum1+=v[i][j];}//cout<<sum1<<endl;if(k>=m||k>=n){cout<<sum1<<endl;return ;}int ans=0;for(int i=0;i<=(1<<n)-1;i++){//memset(lie,0,sizeof(lie));fill(lie.begin(), lie.end(), 0);cnt=0;int sum2=calc(i);sort(lie.begin()+1,lie.begin()+1+m,cmp);//for(int q=1;q<=m;q++)cout<<lie[q]<<" ";if(cnt<=k){int rest=k-cnt;for(int j=1;j<=rest;j++){sum2+=lie[j];}}else continue;ans=max(sum2,ans);}cout<<ans<<endl;
}
int main(){ solve(); return 0;
}//int版
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long ll;
//int sm[N],ps[N];
int n,m,k,cnt;
int v[20][20];
int lie[20];
bool cmp(int a,int b)
{return a>b;
}
int calc(int x)
{int sum2=0;for(int i=1;i<=n;i++){if(((x>>(i-1))&1)==1){for(int j=1;j<=m;j++){sum2+=v[i][j];}cnt++;}else {for(int j=1;j<=m;j++){lie[j]+=v[i][j];}}}return sum2;
}
void solve() {cin>>n>>m>>k;int sum1=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>v[i][j];sum1+=v[i][j];}//cout<<sum1<<endl;if(k>=m||k>=n){cout<<sum1<<endl;return ;}int ans=0;for(int i=0;i<=(1<<n)-1;i++){memset(lie,0,sizeof(lie));cnt=0;int sum2=calc(i);sort(lie+1,lie+1+m);if(cnt<=k){int rest=k-cnt;for(int s=1,j=m;s<=rest;j--,s++){sum2+=lie[j];}}else continue;ans=max(sum2,ans);}cout<<ans<<endl;
}
int main(){ solve(); return 0;
}华华听月月唱歌
题目链接
贪心，sort按第一主键从小到大排序，，这里使用结构体或者其他都行。然后贪婪地往r值大的取找，在所有比前一个r+1小的l的对应的r要尽量大。然后注意特判，一个是看是不是小于r+1（是不是连续的区间）还有一个是如果最右大于n了，就超长度了，那就break掉，
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long ll;
struct NODE
{int l;int r;
}node[N];
bool cmp(NODE n1,NODE n2)
{if(n1.l==n2.l) return n1.r>n2.r;return n1.l<n2.l;
}
int main(){ int m,n,flag=1;cin>>n>>m;for(int i=1;i<=m;i++){cin>>node[i].l>>node[i].r;}sort(node+1,node+1+m,cmp);int cnt=1,l=0,r=0;for(int i=1;i<=m;i++){if(node[i].l<=l+1){r=max(r,node[i].r);}else {l=r;if(node[i].l>l+1){cnt=-1;break;}else{cnt++;r=max(r,node[i].r);} }if(r>=n)break;}if(r<n)cnt=-1;cout<<cnt<<endl;return 0;
}