2012年 普及组T3 摆花
#include
using namespace std;
const int N = 105, MOD = 1e6 + 7;
int n, m; //n种花，m盆
int a[N];
//从第x种花开始，还需要摆y盆，返回所有的方法数
int dfs(int x, int y) {
if (y == 0) return 1; //不需要再摆了
if (x == n && y <= a[x]) return 1; //只剩最后一种花，且数量够
if (x == n && y > a[x]) return 0; //最后一种花数量不够了
int res = 0;
for (int i = 0; i <= min(a[x], y); i ++) {
//如果第 x种花摆 i盆，则接下来从第 x+1种花开始，摆放 y-i盆
//根据加法原理计算总的方案数
res = (res + dfs(x+1, y-i)) % MOD;
}
return res;
}
int main() {
//freopen("flower.in", "r", stdin);
//freopen("flower.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
cout << dfs(1, m);
return 0;
}
#include
using namespace std;
const int N = 105, MOD = 1e6 + 7;
int n, m; //n种花，m盆
int a[N], f[N][N];
//从第x种花开始，还需要摆y盆，返回所有的方法数
int dfs(int x, int y) {
if (f[x][y]) return f[x][y];
if (y == 0) f[x][y] = 1; //不需要再摆了
else if (x == n && y <= a[x]) f[x][y] = 1; //只剩最后一种花，且数量够
else if (x == n && y > a[x]) f[x][y] = 0; //最后一种花数量不够了
else {
for (int i = 0; i <= min(a[x], y); i ++) {
//如果第 x种花摆 i盆，则接下来从第 x+1种花开始，摆放 y-i盆
//根据加法原理计算总的方案数
f[x][y] = (f[x][y] + dfs(x+1, y-i)) % MOD;
}
}
return f[x][y];
}
int main() {
//freopen("flower.in", "r", stdin);
//freopen("flower.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
cout << dfs(1, m);
return 0;
}
2020年 普及组T4 方格取数
#include
#define LL long long
using namespace std;
const int N = 1010;
int n, m;
LL ans = -1e18, a[N][N], s[N][N][3];
bool vst[N][N];
int dx[3] = {-1, 0, 1};
int dy[3] = {0, 1, 0};
void dfs(int x, int y, LL num) {
if (x == n && y == m) {
ans = max(ans, num);
return;
}
for (int i = 0; i < 3; i ++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > n || yy > m) continue;
if (vst[xx][yy]) continue;
if (num + a[xx][yy] <= s[xx][yy][i]) continue;
s[xx][yy][i] = num + a[xx][yy];
vst[xx][yy] = true;
dfs(xx, yy, num + a[xx][yy]);
vst[xx][yy] = false;
}
}
int main() {
// freopen("number.in", "r", stdin);
// freopen("number.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
scanf("%lld", &a[i][j]);
for (int k = 0; k < 3; k ++) {
s[i][j][k] = -1e18;
}
}
}
vst[1][1] = true;
dfs(1, 1, a[1][1]);
printf("%lldn", ans);
return 0;
}
2017年 普及组T3 棋盘
#include
#include
#include
using namespace std;
const int M = 105, N = 1010;
int m, n;
int a[M][M]; //棋盘
int cnt[M][M]; //走到第x行第y列所使用的最少金币数量
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0};
//走到第x行第y列，使用的金币数为coin ,是否使用过魔法
void dfs(int x, int y, int coin, bool magic) {
if (coin >= cnt[x][y]) return; //剪枝，节省运行时间
else cnt[x][y] = coin;
if (x == m && y == m) return; //走到终点，返回
for (int i = 0; i < 4; i ++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > m || yy < 1 || yy > m) continue;
if (a[xx][yy] == 0) { //如果下一个位置无色
if (magic == false) { //如果上一步没有使用魔法
//现在使用魔法，用贪心思想 ,把下一个位置改成相同颜色
a[xx][yy] = a[x][y];
dfs(xx, yy, coin + 2, true);
a[xx][yy] = 0;
}
}
else { //如果下一个位置有颜色
if (a[xx][yy] == a[x][y]) { //和下一个位置的颜色相同
dfs(xx, yy, coin, false);
}
else { //和下一个位置的颜色不同
dfs(xx, yy, coin + 1, false);
}
}
}
}
int main() {
// freopen("chess.in", "r", stdin);
// freopen("chess.out", "w", stdout);
cin >> m >> n;
for (int i = 1; i <= n; i ++) { //有n个格子里有颜色
int x, y, c;
cin >> x >> y >> c; //第x行第y列的颜色是c;
//c=2代表黄色，c=1代表红色, c=0代表无色
a[x][y] = c + 1;
}
memset(cnt, 0x3f, sizeof(cnt));
dfs(1, 1, 0, false);
if (cnt[m][m] == 0x3f3f3f3f) cout << -1 << endl;
else cout << cnt[m][m];
return 0;
}
2012年 普及组T4 文化之旅
#include
using namespace std;
const int N = 105, K = 105, INF = 0x3f3f3f3f;
int n, k, m, s, t;
int c[N], dist[N]; //某个国家的文化，到某个国家的距离
int a[K][K], e[N][N]; //两国之间是否排斥，两国之间的距离
bool h[K]; //已经学过的文化
//到国家x的距离是d
void dfs(int x, int d) {
if (d >= dist[x] || d >= dist[t]) return; //剪枝
dist[x] = d;
if (x == t) return;
for (int i = 1; i <= n; i ++) { //枚举i国
if (e[x][i] == INF) continue; //x,i两国之间没有路
if (h[c[i]]) continue; //已学过该国文化
bool flag = false;
for (int j = 1; j <= k; j ++) { //枚举j文化
if (h[j] && a[c[i]][j] == 1) { //学过j文化且i国的文化排斥j文化
flag = true;
break;
}
}
if (flag) continue;
h[c[i]] = true;
dfs(i, d + e[x][i]);
h[c[i]] = false;
}
}
int main() {
// freopen("culture.in", "r", stdin);
// freopen("culture.out", "w", stdout);
scanf("%d%d%d%d%d", &n, &k, &m, &s, &t);
for (int i = 1; i <= n; i ++) {
scanf("%d", &c[i]); //国家 i的文化为 Ci
}
for (int i = 1; i <= k; i ++) {
for (int j = 1; j <= k; j ++) {
scanf("%d", &a[i][j]); //a[i][j] = 1 表示文化 i 排斥外来文化 j
}
}
memset(dist, 0x3f, sizeof(dist)); //初始化
memset(e, 0x3f, sizeof(e));
for (int i = 1; i <= m; i ++) {
int u, v, d;
scanf("%d %d %d", &u, &v, &d);
e[u][v] = e[v][u] = min(e[u][v], d); //邻接矩阵，去掉重复的边
}
h[c[s]] = true; //学习起点国家的文化
dfs(s, 0); //从起点国家出发
if (dist[t] == INF) printf("-1n");
else printf("%dn", dist[t]);
return 0;
}
2014年 普及组T4 子矩阵
#include
using namespace std;
const int N = 20;
int n, m, r, c, ans = 1e9;
int a[N][N], row[N], col[N];
bool used_x[N], used_y[N];
int calc() {
int res = 0;
for (int i = 1; i < r; i ++) {
for (int j = 1; j <= c; j ++) {
res += abs(a[row[i]][col[j]] - a[row[i+1]][col[j]]);
}
}
for (int j = 1; j < c; j ++) {
for (int i = 1; i <= r; i ++) {
res += abs(a[row[i]][col[j]] - a[row[i]][col[j+1]]);
}
}
return res;
}
//接下来挑选子矩阵的第x行和第y列
void dfs(int x, int y) {
if (x > r && y > c) { //已经挑选出r行c列
ans = min(ans, calc());
return;
}
if (x <= r) {
for (int i = row[x-1] + 1; i <= n; i ++) {
if (!used_x[i]) {
used_x[i] = true;
row[x] = i;
dfs(x + 1, y);
used_x[i] = false;
}
}
}
else {
for (int j = col[y-1] + 1; j <= m; j ++) {
if (!used_y[j]) {
used_y[j] = true;
col[y] = j;
dfs(x, y + 1);
used_y[j] = false;
}
}
}
}
int main() {
// freopen("submatrix.in", "r", stdin);
// freopen("submatrix.out", "w", stdout);
cin >> n >> m >> r >> c;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> a[i][j];
}
}
//接下来挑选子矩阵的第1行和第1列
dfs(1, 1);
cout << ans << endl;
return 0;
}
