11
2025-01-20 20:16:26
发布于：上海
24阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
bool board[102][105];
vector<vector <int> > ans;
vector<int> path;
int n;
bool is_vaild(int x,int y){
for(int i = 1;i < x;i++){
if(board[i][y]) return false;
if(x-i >= 1 && y-i >= 1 && board[x-i][y-i]) return false;
if(x-i >= 1 && y+i >= 1 && board[x-i][y+i]) return false;
}
return true;
}
void dfs(int now)
{
if(now == n+ 1)
{
ans.push_back(path); return ;
}
for(int i = 1;i <= n;++i)
{
if(!is_vaild(now,i)) continue;
board[now][i] = true;
path.push_back(i);
dfs(now+1);
board[now][i] = false;
path.pop_back();
}
}
int main()
{
cin >> n;
dfs(1);
for(int i = 0;i < 3;i++)
{
for(int j = 0;j < n;j++)
{
cout << ans[i][j] << " ";
}cout << endl;
}
cout << ans.size() << endl;
}
#include<bits/stdc++.h>
using namespace std;
int n;//总共饲料数量
int m;//维他命的数量
int b[30];//奶牛要求的各种维他命含量
int a[30][30];//第i种饲料对第j种维他命含量的增加值
int ans[30];//最后选出来总饲料的各种维他命含量
int res = 1e9;//选取最少奶牛数量
bool cow[30];//最后被选择的饲料是哪些
bool ans_cow[30];
void dfs(int u,int cnt){
if(u==n+1){
bool flag = true;
for(int i=1;i<=m;i++)if(ans[i]<b[i])flag = false;
if(flag){
if(res>cnt){
res = cnt;
for(int i=0;i<20;i++)ans_cow[i]=cow[i];
}
}
return;
}
//选饲料
for(int i=1;i<=m;i++)ans[i]+=a[u][i];
cow[u]=1;
dfs(u+1,cnt+1);
for(int i=1;i<=m;i++)ans[i]-=a[u][i];
cow[u]=0;
dfs(u+1,cnt);
}
int main(){
cin>>m;
for(int i=1;i<=m;i++)cin>>b[i];
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dfs(1,0);
cout<<res<<" ";
for(int i=1;i<=n;i++)if(ans_cow[i])cout<<i<<" ";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;//n本书
int m;//m种技能
int x;//想要掌握的技能水平
//m种技能>=x
int a[20][20];//第i本书第j种技能提升的能力为a[i][j]; a[i][0]
int ans[20];//最后每种技能的能力
int res = 1e9;
void dfs(int u,int sum){
if(u==n+1){
bool flag = true;
for(int i=1;i<=m;i++)if(ans[i]<x)flag = false;
if(flag)res = min(res,sum);//最少的花费
return;
}
//选 把技能点加上去，花费也加上去
for(int i=1;i<=m;i++)ans[i]+=a[u][i];
dfs(u+1 ， sum+a[u][0]);
for(int i=1;i<=m;i++)ans[i]-=a[u][i];
dfs(u+1 ， sum);
}
int main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
cin>>a[i][j];
}
}
dfs(1,0);
if(res==1e9)cout<<-1;
else cout<<res;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int g[N][N];
bool st[N][N];
int n;
int ans = 0;
//判断当前矩阵是否合法
bool isValid() {
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - 1; ++j) {
int cnt = 0;
cnt += st[i][j];
cnt += st[i + 1][j];
cnt += st[i][j + 1];
cnt += st[i + 1][j + 1];
if (cnt != 2) {
return false;
}
}
}
return true;
}
void getsum() {
int sum = 0;
for (int i = 0; i < n; i++) { // for循环枚举每一行
for (int j = 0; j < n; j++) { // for循环枚举每一列
if (st[i][j]) { // 如果选了
sum += g[i][j]; // 加上这个位置的能量
}
}
}
ans = max(ans, sum);
}
void dfs(int x, int y) {
//通过id获得下标
if (x == n) {
if (isValid()) {
//记录答案
getsum();
}
return;
}
//当前状态为0不选
st[x][y] = false;
if (y + 1 == n) dfs(x + 1, 0);
else dfs(x, y + 1);
st[x][y] = true;
if (y + 1 == n) dfs(x + 1, 0);
else dfs(x, y + 1);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
dfs(0, 0);
cout << ans << endl;
return 0;
}
100分贪心算法（讲这个）
首先，题目当中的限制条件：每一个 2*2 的子矩阵中，必须恰好包含2瓶药水，我们可以在这个条件的限制下去按行/列去进行选择。
这里先用按列选择进行解释（0表示不选，1表示选择）
对于第一列，因为还不满足2*2的条件，我们可以任意填写：
其中，有两种情况
情况1，即图片1，是按照“一个0一个1”的规律进行的选择
情况2，图片2和3，是不按照“一个0一个1”的规律任意选择的
尝试在第一列的基础上根据限制条件对后续的列进行选择
情况1：对图片1，由于限制条件的存在，它的第二列我们可以有两种选择方式
即 和第一列完全一样的101010 和 第一列完全相反的010101 两种方式。
对于这两种情况，它们的第三列其实也只有：
和第二列完全一样的101010 和 第二列完全相反的010101 两种方式（图略）。
情况2：对于图片2和3，由于限制条件的存在，
它们两个的第二列其实分别只有一种选择方式即 和第一列完全相反
对于他们的第三列：也只有一种选择方式，即 和第二列完全相反
如果再填第四列的话，那就需要和第三列完全相反
填到这里我们会发现：当不按照“一个0一个1”的规律（图片2和3）时，每一行都是按照“一个0一个1”的规律进行的选择。
所以，从第1列开始不按照“一个0一个1”的规律选择 的情况
等价于
从第1行开始按照“一个0一个1”的规律选择 的情况
初步总结
由上述推理过程可知：
从第一列开始 按照“一个0一个1”的规律选择 的情况 + 从第一行开始 按照“一个0一个1”的规律选择 即可得到所有的情况。
后面的列或行，可以按照010101 或 101010 的方式来进行选择
进一步的
其实所有的列都是 既可以选择 101010 的方式，也可以选择 010101 的方式。
具体选择哪一种情况，列与列直接不会互相影响，那么我们就可以根据贪心的思想，选择增加的法力值（这道题目要求的东西） 最大 的一种方式。
最终在按列选择 和 按行选择 中选择较大值即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, ans1, ans2;
int a[N][N], h[N][2], s[N][2];
int main() {
cin >> n;
// 读取输入矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
// 计算 h 和 s 数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//将第j行的101010(即奇数列)和010101(即偶数列)进行分别求和
h[j][i % 2] += a[j][i];
//将第j列的101010(即奇数列)和010101(即偶数行)进行分别求和
s[j][i % 2] += a[i][j];
}
}
// 计算 ans1 和 ans2
for (int j = 1; j <= n; j++) {
ans1 += max(s[j][0], s[j][1]);//按列的贪心选择
ans2 += max(h[j][0], h[j][1]);//按行的贪心选择
}
// 输出结果---按列选择和按行选择中 求较大值
cout << max(ans1, ans2);
return 0;
}
二进制枚举
#include<bits/stdc++.h>
using namespace std;
int n;
int a[20];
bool is_prime(int x){
if(x<=1)return false;
for(int i=2;i<=x-1;i++){
if(x%i==0){
return false;
}
}
return true;
}
int main(){
cin>>n;
//二进制枚举
//n = 3 111 2^3 - 1 <<
for(int i=0;i<n;i++)cin>>a[i];
//000 001 010 011 100 101 110 111
int ans = 0;
//000 - 111
for(int i=0;i<1<<n;i++){
int sum = 0;
for(int j=0;j<n;j++){
if((i>>j)&1==1)sum+=a[j];
}
if(is_prime(sum))ans++;
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个