# APCS 2020/10 題解
## ==人力分配==
### <font color="0E81A6">題目</font>
[人力分配](https://zerojudge.tw/ShowProblem?problemid=f312)
### <font color="0E81A6">核心</font>
迴圈、條件判斷
### <font color="0E81A6">思路</font>

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,A1,A2,B1,B2,C1,C2;
    scanf("%d%d%d%d%d%d%d",&A1,&B1,&C1,&A2,&B2,&C2,&n);
    int maxProfit=INT_MIN,profit;
    for(int i=0;i<=n;i++)
    {
        int Y1=A1*i*i+B1*i+C1,Y2=A2*(n-i)*(n-i)+B2*(n-i)+C2;
        profit=Y1+Y2;
        maxProfit=max(profit,maxProfit);
    }
    printf("%d\n",maxProfit);

}

## ==人口遷移==
### <font color="0E81A6">題目</font>
[人口遷移](https://zerojudge.tw/ShowProblem?problemid=f313)
### <font color="0E81A6">核心</font>
模擬、二維陣列
### <font color="0E81A6">思路</font>
簡易模擬題。

#include<bits/stdc++.h>
using namespace std;
#define N 55
int main()
{
    int R,C,k,m;
    int city[N][N],di[4]={1,0,-1,0},dy[4]={0,1,0,-1},people_num[N][N];
    scanf("%d%d%d%d",&R,&C,&k,&m);
    memset(city,-1,sizeof(city));
    for(int i=1;i<=R;i++)
    {
        for(int j=1;j<=C;j++) scanf("%d",&city[i][j]),people_num[i][j]=city[i][j]/k;
    }
    while(m--)
    {

        for(int i=1;i<=R;i++)
        {
            for(int j=1;j<=C;j++)
            {
                if(city[i][j]==-1) continue;
                for(int d=0;d<4;d++)
                {
                    if(city[i+di[d]][j+dy[d]]!=-1)
                    {
                        city[i+di[d]][j+dy[d]]+=people_num[i][j];
                        city[i][j]-=people_num[i][j];
                    }
                }
            }
        }
        for(int i=1;i<=R;i++)
        {
            for(int j=1;j<=C;j++) people_num[i][j]=city[i][j]/k;
        }
    }
    int max_n=0,min_n=INT_MAX;
    for(int i=1;i<=R;i++)
    {
        for(int j=1;j<=C;j++)
        {
            if(city[i][j]==-1) continue;
            max_n=max(city[i][j],max_n);
            min_n=min(city[i][j],min_n);
        }
    }
    printf("%d\n%d\n",min_n,max_n);

}

## ==勇者修練==
### <font color="0E81A6">題目</font>
[勇者修練](https://zerojudge.tw/ShowProblem?problemid=f314)
### <font color="0E81A6">核心</font>
dp、模擬
### <font color="0E81A6">思路</font>
一列一列考慮，任一點有可能從左或右或上過來，而頭尾只會從上下來。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define M 55
int A[N];
int dp[M][N]={0};
int m,n;
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) scanf("%d",A+j);

        int l[N]={0},r[N]={0};
        for(int j=1;j<=n;j++)
        {
            if(j==1) l[j]=dp[i-1][j]+A[j];
            else l[j]=max(dp[i-1][j],l[j-1])+A[j];
        }
        for(int j=n;j>=1;j--)
        {
            if(j==n) r[j]=dp[i-1][j]+A[j];
            else r[j]=max(dp[i-1][j],r[j+1])+A[j];
        }
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=max(l[j],r[j]);
        }
    }
    int sum=INT_MIN;
    for(int j=1; j<=n; j++)
    {
        sum=max(dp[m][j],sum);
    }
    printf("%d\n",sum);


}

## ==低地距離==
### <font color="0E81A6">題目</font>
[低地距離](https://zerojudge.tw/ShowProblem?problemid=f315)
### <font color="0E81A6">核心</font>
BIT
### <font color="0E81A6">思路</font>
[大佬思路](https://hackmd.io/@QWERTYPIG/Sy3rQgPb2#%E7%AC%AC%E5%9B%9B%E9%A1%8C-%E4%BD%8E%E5%9C%B0%E8%B7%9D%E9%9B%A2)

#include<bits/stdc++.h>
using namespace std;
long long ans=0;
pair<int,int> arr[100010];
struct BIT
{
    int sz;
    vector<int> dat;
    void init(int n)
    {
        sz=n;
        dat.assign(n+1,0);
        return;
    }
    void upd(int id,int x)
    {
        for(int i=id;i<=sz;i+=i&-i) dat[i]+=x;
        return;
    }
    int sum(int id)
    {
        int ans=0;
        for(int i=id;i>0;i-=i&-i) ans+=dat[i];
        return ans;
    }
}bit;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)
    {
        int a;
        scanf("%d",&a);
        if(arr[a].first==0) arr[a].first=i;
        else arr[a].second=i;
    }
    bit.init(2*n);
    for(int i=1;i<=n;i++)
    {
        ans+=bit.sum(arr[i].second-1)-bit.sum(arr[i].first);
        bit.upd(arr[i].first,1);
        bit.upd(arr[i].second,1);
    }
    printf("%lld\n",ans);
}