colorf slimes（刷题总结）_colourful slimes

#colorful slimes(DP + 思维）

题目描述
Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him ai seconds.

Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N−1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.

Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints
2≤N≤2,000
ai are integers.
1≤ai≤109
x is an integer.
1≤x≤109
输入
The input is given from Standard Input in the following format:

N x
a1 a2 … aN
输出
Find the minimum time that Snuke needs to have slimes in all N colors.
样例输入 Copy
2 10
1 100
样例输出 Copy
12
提示
Snuke can act as follows:

Catch a slime in color 1. This takes 1 second.
Cast the spell. The color of the slime changes: 1 → 2. This takes 10 seconds.
Catch a slime in color 1. This takes 1 second.
本题大意是Snuke 想要获得N种颜色，他有两种操作，一是直接付出对应颜色的代价来获得，二是所有获得的颜色i变成颜色i + 1。
所以想要获得颜色i 有两种方法
1.直接付出相应代价。
2.进行操作二j次使 i-j（已经获得）变成 i 。
不妨设进行操作二的次数为j，显然想要以最小的代价获得全部的颜色，只需要最多n-1次操作二即可。
于是有 0 <= j <= n - 1 。
我们发现进行操作二的次数最终会在总代价上加上 j * x，
不妨设dp[ i ] [ j ]表示进行j次操作时获得第i个颜色的最小代价。
于是可以通过枚举j来获得操作次数为j时获得每种颜色付出的最小代价，最终加和即可。
状态转移方程 dp[ i ] [ j ] = min ( a[ i - j ] , dp [ i ] [ j - 1 ])
a[i - j ] 表示在获得第i个颜色时进行了第j次操作（已经做了j - 1 次）并以后移了j次的代价获得，
dp[ i ] [ j - 1 ] 表示在获得第i个颜色时（已经进行了j-1次操作），以当前代价直接获得。
下面贴代码
下面展示一些 内联代码片。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int ll ;
 
int dp[2020][2020];
ll mi = 0x3f3f3f3f3f3f3f3f ;
int main()
{
ll n , x ,sum;
scanf("%lld%lld",&n,&x) ;
for(int i = 1 ; i <= n ; i ++)
scanf("%d",&dp[i][0]) ;//这里进行了空间优化，直接用dp[i][0] 表示a[i]即可 。 
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= n - 1 ; j ++){
        int k = i - j ;
        if(k <=0) k += n  ;//指向后移j次的代价可能会循环
        dp[i][j] = min(dp[i][j-1],dp[k][0]) ;
    }
for(int i = 0 ; i <= n - 1; i ++){
        sum = 0 ;
        for(int j = 1 ; j <= n ; j ++)
            sum += dp[j][i] ;
            sum += i * x ;//最后求得各个状态付出代价总和
            mi = min(mi,sum) ;//取得其中的最小值
    }
printf("%lld\n",mi) ;
return 0 ； 
}
var foo = 'bar';
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30