A. 菜
暴力做法：2^n枚举哪些人是正向上菜的，然后记录答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 20;
const int N = 1e6 + 2;
const ll mod = 1e9 + 7;
int ans, res, n, c[maxn], las;
bool v[maxn];
vector<int> a, b;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void Color(int x)
{
int k = 0;
while(x)
{
k++;
if(x & 1) a.push_back(k), v[k] = 1;
//else b.push_back(k);
x >>= 1;
}
}
int main()
{
n = read();
for(int i=1; i<=n; i++)
{
c[i] = read();
}
int Max = (1<<n)-1;
for(int i=0; i<=Max; i++)
{
//printf("New case:\n");
//memset(v, 0, sizeof(v));
a.clear(); b.clear(); res = 0;
//Color(i);
/*printf("a:\n");
for(int j=0; j<a.size(); j++)
{
printf("%d ", a[j]);
}
printf("\n");
for(int j=n; j>=1; j--)
{
if(!v[j]) b.push_back(j);
}
printf("b:\n");
for(int j=b.size()-1; j>=0; j--)
{
printf("%d ", b[j]);
}
printf("\n");*/
for(int j=0; j<n; j++)
{
if(i & (1<<j)) a.push_back(j+1);
else b.push_back(j+1);
}
int sz = a.size();
las = 0;
for(int j=0; j<sz; j++)
{
res += c[a[j]]*las;
las = c[a[j]];
}
sz = b.size();
for(int j=sz-1; j>=0; j--)
{
res += c[b[j]]*las;
las = c[b[j]];
}
ans = max(ans, res);
}
printf("%d\n", ans);
return 0;
}
TLE 30
我才是菜。
看半天题解看不懂，对着代码发半天呆。
所以转移方程的意思大概就是，默认第i个人反向，第一行是假设第i+1个人反向，所以i上一个上菜的人是i+1，第二行假设第i+1个人正向，所以i+1上一个上菜的人是i+1。
最后统计答案大概就是，f[n][i]是准备好要转移到f[n+1][i]的，后面没有n+1了，但是i到n的贡献没有加上，还要把它加进去。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505;
int n, h[maxn], ans, f[maxn][maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read();
for(int i=1; i<=n; i++)
{
h[i] = read();
}
for(int i=1; i<=n; i++)
{
for(int j=0; j<i; j++)
{
f[i+1][j] = max(f[i][j]+h[i+1]*h[i], f[i+1][j]);
f[i+1][i] = max(f[i][j]+h[i+1]*h[j], f[i+1][i]);
}
}
for(int i=0; i<n; i++)
{
ans = max(ans, f[n][i]+h[n]*h[i]);
}
printf("%d\n", ans);
return 0;
}
View Code
B. 渔船
听说用到了费用流！？咕了咕了……
A. 蛋糕
啊这，所以我参加考试的意义原来就是垫个底拉长一下排行榜……连dfs都没想到直接打算枚举第一个后来就让他们俩全都去选最大的，但是据说caorong的贪心有分，我的贪心连样例都过不了……算了反正也是错误思路就不说了。
然后我看到了题解依然不知道怎么转移……
f[i][j]转移的话只能是每次多选了一个a[i]或一个a[j]，选a[i]的话就要看另一个人是选了a[i+1]还是a[j]，选a[j]的话就要看另一个人选了a[i]还是a[j-1]。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4005;
const int N = 1e6 + 2;
const ll mod = 1e9 + 7;
int n;
ll a[maxn], f[maxn][maxn], ans;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read();
for(int i=1; i<=n; i++) a[i] = read();
for(int i=1; i<=n; i++) a[i+n] = a[i];
for(int i=1; i<=n+n; i++) f[i][i] = a[i];
for(int d=2; d<=n; d++)
{
for(int i=1, j=i+d-1; j<=n+n; i++,j++)
{
f[i][j] = max(f[i][j], a[i]+(a[i+1]>a[j]?f[i+2][j]:f[i+1][j-1]));
f[i][j] = max(f[i][j], a[j]+(a[i]>a[j-1]?f[i+1][j-1]:f[i][j-2]));
}
}
for(int i=1; i<=n; i++)
{
ans = max(ans, f[i][i+n-1]);
}
printf("%lld\n", ans);
return 0;
}
%%% lyin
B. 游戏
粘一些大佬的题解好了，该睡觉了……
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4000005;
const int N = 1e6 + 2;
const ll mod = 1e9 + 7;
int x, y, n, tot;
ll a, b, c, d[505][505], ans, dis[maxn];
bool vis[maxn];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
priority_queue<pair<ll, int> > q;
struct node
{
int x, y;
}lilulu[maxn];
queue<pair<int, int> > que;
struct node2
{
int next, to; ll w;
}e[maxn];
int head[maxn], len;
void add(int u, int v, ll w)
{
e[++len].to = v; e[len].next = head[u]; e[len].w = w;
head[u] = len;
}
int id(int i, int j, int k)
{
return (i-1)*y+j+k*tot;
}
void dij(int s)
{
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
memset(vis, 0, sizeof(vis));
q.push(make_pair(-dis[s], s));
while(!q.empty())
{
int x = q.top().second; q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i=head[x]; i; i=e[i].next)
{
int y = e[i].to; ll z = e[i].w;
if(dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
q.push(make_pair(-dis[y], y));
}
}
}
}
int main()
{
scanf("%d%d", &x, &y);
x++; y++;
tot = x*y;
memset(d, 0x3f, sizeof(d));
scanf("%lld%lld%lld", &a, &b, &c);
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
scanf("%d%d", &lilulu[i].x, &lilulu[i].y);
lilulu[i].x++; lilulu[i].y++;
que.push(make_pair(lilulu[i].x, lilulu[i].y));
d[lilulu[i].x][lilulu[i].y] = 0;
}
while(!que.empty())
{
pair<int, int> pa = que.front();
que.pop();
for(int i=0; i<4; i++)
{
int p = pa.first+dx[i], q = pa.second+dy[i];
if(p > 0 && q > 0 && p <= x && q <= y)
{
if(d[p][q]>d[pa.first][pa.second]+1)
{
d[p][q] = d[pa.first][pa.second]+1;
que.push(make_pair(p, q));
}
}
}
}
for(int i=1; i<=x; i++)
{
for(int j=1; j<=y; j++)
{
if(i-1>0) add(id(i, j, 0), id(i-1, j, 0), a);
if(i+1<=x) add(id(i, j, 0), id(i+1, j, 0), a);
if(j-1>0) add(id(i, j, 1), id(i, j-1, 1), a);
if(j+1<=y) add(id(i, j, 1), id(i, j+1, 1), a);
add(id(i, j, 2), id(i, j, 0), b);
add(id(i, j, 2), id(i, j, 1), b);
for(int k=0; k<4; k++)
{
int p = i+dx[k], q = j+dy[k];
if(p > 0 && q > 0 && p <= x && q <= y)
{
add(id(i, j, 2), id(p, q, 2), c);
}
}
add(id(i, j, 0), id(i, j, 2), c*d[i][j]);
add(id(i, j, 1), id(i, j, 2), c*d[i][j]);
}
}
dij(id(lilulu[1].x, lilulu[1].y, 2));
ans = min(dis[id(lilulu[n].x, lilulu[n].y, 2)], min(dis[id(lilulu[n].x, lilulu[n].y, 1)], dis[id(lilulu[n].x, lilulu[n].y, 0)]));
printf("%lld\n", ans);
return 0;
}
View Code
标签：ch,const,int,ll,maxn,&&,加试,邀请赛,dis From： https://www.cnblogs.com/Catherine2006/p/16603458.html