USACO analysis
李若谷 |
14 Apr 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目大意
N个点M条边的有向图，每个点都有一个值$m_i$。求从点1出发回到点1的m的总和减去$sum^2$(走过的边数)*c(一个给定的常数)的最大值
思路
$dp(i,j)$代表从1出发，经过了i条边，到点j的m总和的最大值。 可以得出$dp(i,j) = \max$$(dp(i-1,k)) +m_j$ 其中k是所有能直接到j的点。 那么答案就是$\max dp(i,1) - i^2*c$ i也就是经过的边数是不确定的。 但是可以看出，边数最大的情况就是c为1, $m_i = 1000$（题目给出的m的最大值）的图。 这样的图可以得到方程$f(x) = 1000x - x^2$ 其中x代表走过的边数，f(x)代表经过x条边后的值，由于图是固定的这个值也是固定的。 在这个方程中若要让f(x)>=0， x取的最大值是1000，所以最多经过1000条边。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1005;
const int maxm = 2005;
int c,n,m;
int money[maxn];
int ans = 0;
inline int read()
{
int sum=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
sum=sum*10+(ch^48),ch=getchar();
return sum;
}
struct Edge{
int to;
int next;
}edge[maxm];
int head[maxn];
int cnt = 0;
int dp[1005][maxn];
void add_edge(int x,int y)
{
edge[++cnt].to = y;
edge[cnt].next = head[x];
head[x] = cnt;
}
int main()
{
n=read();
m=read();
c=read();
for(int i=1;i<=n;i++){
scanf("%d",&money[i]);
}
for(int i=1;i<=m;i++)
{
int x,y;
x=read();
y=read();
add_edge(y,x);
}
memset(dp,-1,sizeof(dp));
dp[0][1] = 0;
for(int i=1;i<=1000;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=head[j];k;k=edge[k].next){
int las = edge[k].to;
if(dp[i-1][las]!=-1)
dp[i][j] = max(dp[i][j],dp[i-1][las] + money[j]);
}
}
ans = max(ans,dp[i][1]-c*i*i);
}
cout<<ans<<endl;
return 0;
}
时间复杂度
$O(n^2)$
