思路

这题其实还是很好想的（我还交了7发...） 首先肯定会想到贪心，直接暴力上，时间复杂度是 $O(n)$ 可把孩子高兴坏了，可是很抱歉，这样是错的，只能拿到 $20$ 分的好成绩

那该怎么做呢？

老老实实dp吧!

其实这题的难点是如何定义状态，我定义了思维，其实重要的也就两维 $f[i][j]$ 表示 $i$ 杯红茶 $j$ 被绿茶的最小代价，而后面的 $f[i][j][k][r]$ 的 $k$ 和 $r$ 就是两者连续多少次了，状态转移也很好想，只需要注意判断不能再用哪种颜色的茶了就行。

$20$的贪心

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e3+1;
int m,n,x,z,lv[N],re[N],tot1,tot2,now,mm,s,k1,k2,sum;
signed main()
{
        cin >> m >> n;
        for (int i=1; i<=n; i++)
        {
                cin >> x >> z;
                if (z==0) lv[++tot1]=x;
                else re[++tot2]=x;
        }
        sort(lv+1,lv+1+tot1);
        sort(re+1,re+1+tot2);

        // for(int i=1; i<=tot1; i++) cout << re[i] << endl;
        k1=k2=1; mm=0; s=-1;//k1,k2为指针，mm为持续多久选同样的，s是上一个选了什么
        while (m--)
        {
                if (lv[k1]<re[k2]) now=0;
                else now=1;
                // if (k1>tot1) now=1;
                // if (k2>tot2) now=0;
                if (now==s&&mm==2)
                {
                        if (now) sum+=(m+1)*lv[k1],k1++,s=0;
                        else sum+=(m+1)*re[k2],k2++,s=1;
                        mm=1;
                        // cout << sum << endl;
                        continue;
                }
                if (now==s)
                {
                        mm++;
                        if (now) sum+=(m+1)*re[k2],k2++;
                        else sum+=(m+1)*lv[k1],k1++;
                        // cout << sum << endl;
                        continue;
                }
                else
                {
                        mm=1;
                        s=now;
                        if (now) sum+=(m+1)*re[k2],k2++;
                        else sum+=(m+1)*lv[k1],k1++;
                        // cout << sum << endl;
                }
        }
        cout << sum;
}

AC Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e3+1;
int m,n,x,z,lv[N],re[N],tot1,tot2,now,mm,s,k1,k2,sum,f[N][N][5][5],ans;
void init()
{
        for(int i=0; i<=m; i++)
                for(int j=0; j<=n; j++)
                        for(int t=0; t<=2; t++)
                                for(int l=0; l<=2; l++)
                                        f[i][j][t][l]=1e16+7;
        f[0][0][0][0]=0;
}
signed main()
{
        cin >> m >> n;
        for(int i=1; i<=n; i++)
        {
                cin >> x >> z;
                if (z) lv[++tot1]=x;
                else re[++tot2]=x;
        }
        sort(lv+1,lv+1+tot1);
        sort(re+1,re+1+tot2);

        for(int i=tot1+1; i<=n; i++) lv[i]=1e16+7;
        for(int i=tot2+1; i<=n; i++) re[i]=1e16+7;
        init();

        for(int i=1; i<=m; i++)
        {

                for(int j=1,ad=lv[j]*(m-i+1),bd=re[i-j]*(m-i+1); j<=i; j++,ad=lv[j]*(m-i+1),bd=re[i-j]*(m-i+1))
                        f[i][j][1][0]=min(f[i-1][j-1][0][0],min(f[i-1][j-1][0][1],f[i-1][j-1][0][2]))+ad,
                        f[i][j][2][0]=f[i-1][j-1][1][0]+ad,
                        f[i][j][0][1]=min(f[i-1][j][0][0],min(f[i-1][j][1][0],f[i-1][j][2][0]))+bd,
                        f[i][j][0][2]=f[i-1][j][0][1]+bd;
                int bd=re[i]*(m-i+1);
                f[i][0][0][1]=min(f[i-1][0][0][0],min(f[i-1][0][1][0],f[i-1][0][2][0]))+bd,
                f[i][0][0][2]=f[i-1][0][0][1]+bd;
        }
        ans=1e16+7;
        for(int i=0; i<=tot1; i++)
                ans=min(ans,f[m][i][0][0]),ans=min(ans,f[m][i][0][1]),ans=min(ans,f[m][i][0][2]),ans=min(ans,f[m][i][1][0]),ans=min(ans,f[m][i][2][0]);
        cout << ans;
}

还有别忘了开 $longlong$ ...